38. Формулы алгебры логики, их таблицы истинности.

Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно. Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.

Определим по индукции понятие формулы алгебры логики:

1. Любая логическая переменная является формулой (атомарной);

2. Если φ и ψ – формулы, то выражения являются формулами;

3. Никаких других формул, кроме построенных по пп 1, 2 нет.

Символы называются логическими операциями или связками: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно соответствует набор значений переменных, составляющих формулу, и соответствующее значение полученной формулы:

Другие логические операции:

1. штрих Шеффера, или антиконъюнкция;

2. стрелка Пирса, или антидизъюнкция;

3. кольцевая сумма или сложение по модулю 2.

Некоторые соглашения о приоритете операций:

1. Внешние скобки не пишутся;

2. Вводится отношение:

Для равносильных связок расстановка скобок выполняется слева направо.