logo
Дискретная математика ПМ / Пособие по Дискретной математике

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

Алгебра логики рассматривает логические формулы как алгебраические выражения, которые можно преобразовать по определенным правилам. Знаки операций обозначают логические операции (логические связки).

В формулах алгебры логики переменные – это высказывания. Они принимают только два значения – ложь и истина, которые обозначаются либо 0 и 1, либо Л и И, либо false и true.

Каждая формула задает логическую функцию: функцию от логических переменных, которая сама может принимать только два логических значения.

Таблица функций одной переменной:

Константа 0:

Тождество:

Отрицание:

Константа 1:

0

0

0

1

1

1

0

1

0

1

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

Дизъюнкция

Конъюнкция

Импликация

Эквивалентность

(равнозначность)

Неравнозначность

(сложение по модулю 2)

Штрих Шеффера

(НЕ – И)

Стрелка Пирса

(НЕ – ИЛИ)

0

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

0

1

0

1

0

0

0

1

1

0

1

1

1

1

1

1

0

0

0

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

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

Формула F называется тождественно истинной или тавтологией, если она принимает значение «истина» независимо от значений входящих в нее высказывательных переменных. Формула F называется выполнимой, если при некоторых значениях ее высказывательных переменных она принимает значение «истина». Такой набор значений высказывательных переменных называется моделью формулы F.