Равносильные формулы и их доказательство

Алгебра высказываний также как и булева алгебра использует два элемента: «истина», «ложь». В алгебре высказываний рассматриваются вопросы, связанные с образованием сложных высказываний. Если, у нас есть несколько высказываний, то при помощи логических связок (конъюнкции, дизъюнкции, импликации и эквивалентности) и при помощи операций из них можно образовывать различные, новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные высказывания называются сложными.

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

· на улице светит солнце, и в аудитории идут занятия;

· на улице светит солнце, или в аудитории идут занятия;

· если на улице светит солнце, то в аудитории идут занятия. и. т. д.

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

Рассмотрим некоторые определения.

Алфавит – любое непустое множество.

Символ – элемент алфавита.

Произвольная конечная последовательность символов, называется, словом или выражением.

Выражение называется формулой, если оно удовлетворяет следующим требованиям:

1. любая высказывательная переменная есть формула;

2. если X и Y – формулы, то выражения

…Y

тоже являются формулами.

Упорядоченный набор высказывательных переменных называется списком.

Оценка из списка – это сопоставление каждой переменной ее истинного значения.