30. Методы доказательства. Обратное рассуждение.
Обратное рассуждение. Предполагаем, что высказывание Qложно и показываем ошибочностьP. То есть фактически, прямым способом проверяем истинность импликации, что логически эквивалентно истинности исходного утверждения.
31. Предикаты. Кванторы.
Предикатом называется утверждение, содержащее переменные, принимающее значение истины или лжи в зависимости от значений переменных.
Существуют некоторые логические операторы, называемые кванторами, применение которых к предикатам превращает последние в ложные и истинные высказывания.
32. Исчисление предикатов. Диаграммы Эйлера.
Исчисление предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высшего порядка.
Символы переменных (обычно
и т. д.),Пропозициональные связки:
,Кванторы: всеобщности
и
существования
,Служебные символы: скобки и запятая.
33. Двоичная арифметика. Булевы функции.
Булева алгебра изучает множество {0 , 1} с определенными на нем операциями дизъюнкции, конъюнкции и отрицания.
Булевой функцией от nбулевых переменных p1p2 ….. называется такая функция f : ВN—>B, что f(p1,p2,p3..) — булево выражение. Бу́лева фу́нкцияотnаргументов — вдискретной математике— отображениеBn→B, гдеB= {0,1} —булево множествов. …..любую булеву функцию можно единственным образом представить в виде дизъюнкции минтермов
34. Реализация булевых функций формулами.
Так же, как составные высказывания строятся из более простых, с помощью логических операций, можно комбинировать булевы переменные с помощью булевых опе¬раций, получая булевы выражения, которые называются формулами.
Всякой формуле однозначно соответствует некоторая функция, при этом говорят, что формула реализует функцию.
35. Днф и кнф.
Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Любую булеву функцию можно привести к КНФ( конъюнктивно нормальной форме.) или ДНФ (дизъюнктивно нормальной форме.)
36. Карта Карно.
Карта Карно – это таблица, каждая ячейка которая содержит элементарную конъюнкцию. Для заполнение карты Карно значениями сначала необходимо перенести из таблицы истинности ДНФ.
37. Понятие алгоритма. Вычислимые функции.
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможно ли написать алгоритм, вычисляющий эту функцию.