🗊Презентация Алгебра высказываний

АЛГЕБРА ВЫСКАЗЫВАНИЙ Глава 1, стр. 7

Алгебра высказываний Высказывание — это утверждение, о котором можно сказать, что оно истинно или ложно. Логические операции - отрицание « ¬ », конъюнкция – двухместная логическая операция ∧ («и») – по высказываниям А, В определяет высказывание А ∧ В («А и В»), которое истинно тогда и только тогда, когда оба высказывания А, В истинны. Дизъюнкция – двухместная логическая операция ∨ («или») – по высказываниям A, B определяет высказывание A∨В («A или B»), которое истинно тогда и только тогда, когда хотя бы одно из высказываний A, B – истинно. Импликация – двухместная логическая операция → («если…, то…») – по высказываниям А, В определяет высказывание А→В («если А, то В»), которое ложно тогда и только тогда, когда А - истинно, В – ложно. А называется посылкой, В – заключением. Эквиваленция – двухместная логическая операция ↔ («если и только если…, то…») определяет высказывание А ↔ В («если и только если А, то В»), которое истинно тогда и только тогда, когда А, В оба истинны или оба ложны.

Рекурсивное определение формулы алгебры логики: одна логическая переменная; формула, заключенная в круглые скобки; две формулы, между которыми стоит знак бинарной логической операции; формула, перед которой стоит знак унарной логической операции. Для того, чтобы в формулах не использовать много скобок, при записи логических формул используют приоритеты операций. Максимальный приоритет у функции отрицания. Затем по приоритету следует конъюнкция, после нее – дизъюнкция. У всех остальных операций одинаковый приоритет, который меньше приоритета дизъюнкции.

Свойства булевых функций Формула называется тождественно истинной, если при всех значениях входящих в нее переменных она принимает значение true. Формула называется тождественно ложной или невыполнимой, если при всех значениях входящих в нее переменных она принимает значение false. Формула называется выполнимой, если при некоторых значениях входящих в нее переменных она принимает значение true. Определение 1.1. Две булевых функци и равны, если на всех наборах значений аргументов их значения совпадают.

Основные логические эквивалентности – примеры тавтологий На основе этих правил можно легко выполнять преобразования или доказывать истинности формул, например:

Нормальные формы Теорема 1.1 (о конъюнктивном разложении). Любая булева функция может быть представлена как Определение 1.2. Представление логической функции в виде конъюнкции, каждый конъюнкт которой является дизъюнкцией взятых с отрицанием или без отрицания логических переменных, называется конъюнктивной нормальной формой этой функции (КНФ). Если каждый конъюнкт содержит по одной все переменные, то КНФ называется совершенной конъюнктивной нормальной формой (СКНФ).

СКНФ Рассмотрим, например, построение СКНФ для следующей функции: Функция равна false в трех точках, следовательно, представление функции в форме СКНФ имеет три конъюнкта:

Нормальные формы Теорема 1.2 (о дизъюнктивнойм разложении). Любая булева функция может быть представлена как Определение 1.3. Представление логической функции в виде дизъюнкции, каждый дизъюнкт которой является конъюнкцией взятых с отрицанием или без отрицания логических переменных, называется дизъюнктивной нормальной формой этой функции (ДНФ). Если каждый дизъюнкт содержит по одной все переменные, то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Понятие базиса Определение 1.4. Функционально полным набором или базисом называется такое множество логических функций, суперпозицией которых может быть построена любая логическая функция. Определение 1.5. Базис называется минимальным, если при удалении любой функции из базиса он базисом не является. Понятие базиса имеет важное практическое значение: на основе функциональных блоков, соответствующих функциям базиса, можно реализовать любую логическую схему. Очевидно, что множество булевых функций НЕ, И, ИЛИ является базисом. Базис Буля — не единственно возможный. Более того, он не является минимальным. базис НЕ–ИЛИ и базис НЕ–И. Оба эти базиса являются минимальными, так как удаление любой функции из этих базисов не позволяют построить все логические функции даже двух переменных.

Теорема 1.3 (теорема Поста) Для того, чтобы множество B логических функций являлось базисом, необходимо и достаточно выполнение следующих условий: B содержит по крайней мере одну функцию, не сохраняющую true, т.е. Хотя бы одна функция базиса ; B содержит по крайней мере одну функцию, не сохраняющую false, т.е. хотя бы одна функция базиса ; B содержит по крайней мере одну немонотонную функцию (функция называется монотонной, если для всех упорядоченных пар наборов значений аргументов выполняется отношение B содержит по крайней мере одну несамодвойственную функцию (функция называется самодвойственной, если для любого набора значений аргументов значения функции удовлетворяют отношению ; B содержит по крайней мере одну нелинейную функцию (функция называется линейной, если может быть представлена полиномом относительно операции:

Базисы – базис Жегалкина, содержащий функции x&y, и константную функцию true, – базис Шеффера, содержащий единственную функцию x|y, – базис Пирса, содержащий единственную функцию x ↓ y, – базис, содержащий функции x →y и ¬x, – базис, содержащий функции x&y и ¬x, – базис, содержащий функции x v y и ¬x.

Упражнения Задание №1. Пусть A обозначает высказывание “Я увлекаюсь теннисом”, а B обозначает высказывание “Я изучаю программирование”. Дайте словесную формулировку следующих высказываний: ¬A ; ¬¬B; AB; A B ; A¬B; ¬AB ; 7) ¬A  ¬B; A→ B; A↔ B ; ¬A B.

Упражнения

Упражнения 3. Постройте таблицы истинности для высказываний 4. Постройте СКНФ и СДНФ для следующих высказываний

Упражнения Доказать, что формула является тавтологией, без построения таблицы истинности. Во всех формулах выделить всевозможные подформулы. 1) (A→ B)→((A C)→(B  C)). 2) ((A→ B)  (B→C))→(A→C). 3) ((A  B)↔ B)↔(B→ A). 4) (A→ B)↔(¬B→¬A). 5) ((A→ B)→ A)→ A. 6) ¬A→(A→ B) . 7) (¬A→ B)  ¬(A B). 8) (A→ B)→(¬B→¬A). 9) (A→C)→((B→C)→(A B→C)). 10) (A→ B)→((A  C)→(B  C)).

Упражнения Доказать, что первая формула логически влечет вторую формулу. 1) ¬(A B); ¬(A B). 2) A; B→ A. 3) (A→ B)(B→C); A→C . 4) A→ B; (AC)→(B C). 5) A→C ; (B→C)→(A B→C). 6) A; ¬¬A. 7) ¬A; A→ B. 8) A→ B; (A C)→(B  C). 9) A→ B; ¬B→¬A. 10) A→(B→C); (A→ B)→(A→C).