Алгебра логики.

Под высказыванием понимается предложение, относительно которого можно сказать истинно оно или ложно. Вводятся обозначения: 1 – “истинно”, 0 – “ложно”.Переменная, принимающая значения из множества {0, 1}, называется высказывательной переменной. Вводятся обозначения: . Алгебраические операции, определённые на множестве {0, 1}, называются логическими операциями. - арная логическая операция: Логические операции.

Отрицанием высказывания называется высказывание, истинное, когда высказывание ложно, и ложное – в противном случае. Конъюнкцией двух высказываний и называется высказывание, истинное, когда оба высказывания истинны, и ложное – во всех других случаях. Конъюнкция называется логическим умножением. ; = min{ , } Дизъюнкцией двух высказываний и называется высказывание, ложное в случае, когда оба высказывания ложны, и истинное – во всех других случаях. Дизъюнкция называется логическим сложением. ; = max{ , } Импликацией двух высказываний и называется высказывание, ложное, когда истинно, а ложно; во всех других случаях - истинное. (если , то ). Эквиваленцией двух высказываний и называется высказывание, истинное, когда истинностные значения и совпадают, и ложное - в противном случае. (тогда и только тогда, когда). Альтернативной дизъюнкцией двух высказываний и называется высказывание, истинное, когда истинностные значения и не совпадают, и ложное - в противном случае. (или , или ). = - отрицание эквиваленции. = - сложение по модулю 2. - стрелка Пирса. = - отрицание дизъюнкции. - штрих Шеффера. = - отрицание конъюнкции. Формулы алгебры высказываний - это некоторые конструкции, построенные с помощью логических операций и высказывательных переменных, которые имеют смысл. Высказывания и высказывательные переменные являются формулами. Установим порядок выполнения операций в логических формулах:

1) , 2) , потом дизъюнкция , , , .Формула называется тождественно истинной (тождественно ложной), если она принимает значение 1 (0) при всех значениях высказывательных переменных, входящих в эту форму.Формула, не являющаяся ни тождественно истинной, ни тождественно ложной, называется выполнимой. Формулы называются эквивалентными, если они принимают одинаковые значения истинности при одинаковых наборах значений истинности, содержащихся в них высказывательных переменных.Формулы, в которые входят конъюнкция, дизъюнкция, отрицание, причём отрицание относится только к высказывательным переменным, называются приведёнными формулами. Теорема. Для любой формулы алгебры высказывания существует эквивалентная (равносильная) ей приведённая формула.

3. Основные законы логики.

1. Свойства констант

2. Закон противоречия

Закон исключения третьего

3. Закон двойного отрицания

4.

5. Коммутативный закон дизъюнкции и конъюнкции

6. Ассоциативные законы

7. Дистрибутивные законы

8. Закон де Моргана

4. Логические функции. Совокупность {0, 1, *, +, -} называют алгеброй логики.

Логической функцией от n – переменных (функцией алгебры логики или булевой функцией) называется n- арная функция, заданная на множестве {0, 1}. , где - высказывательные переменные, , . Все логические функции образуют класс , где - целое, положительное число.Логическая функция может быть задана таблицей, в левой части которой указаны всевозможные двоичные наборы значений её переменных, в правой части соответствующие значения функций.

Наборы значений переменных, на которых функция принимает значение 1, называются единичными наборами, а их совокупность единичным множеством данной функции. Наборы значений переменных, на которых функция принимает значение 0, называются нулевыми наборами, а их совокупность нулевым множеством. Теорема. Существует 2в степени 2ⁿбулевых функций от n переменных. (|P₂(n)|=2 в степени 2ⁿ