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

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

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

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

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

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

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

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

φ	ךφ		φ	ψ

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

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

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

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

φ	ψ	φ|ψ

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

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

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

	ך
	|	↓
	→
↔

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