Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Классификация формул алгебры высказываний.

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

Формула Х называется тождественно ложной, если она принимает значение 0 при всех наборах значений входящих в нее переменных.

Две формулы алгебры логики X и Y называются рав­носильными, если при любых значениях входящих в них высказывательных переменных логические значения высказываний, получающихся из формул X и Y, совпадают. Для указания равносильности формул использу­ют обозначение .

Существует тесная связь между понятием равно­сильности формул и понятием тавтологии.

Признак равносильности формул. Две формулы X и Y алгебры высказываний равносильны тогда и только тогда, когда формула является тавто­логией, и обратно, если формула – тавтология, то формулы X и Y равносильны.

Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: ;

б) симметрично: если , то ;

в) транзитивно: если и , то .

3.2 Примеры равносильных формул. Равносильности формул алгебры логики часто называют законами логики.

Вот наиболее важные из них:

1. – закон тождества.
2. – закон противоречия.
3. – закон исключенного третьего.
4. – закон двойного отрицания.
5. .
6. .
7. .
8. .
9. ; – законы идемпотентности.
10. ; – законы поглощения.
11. ; – законы склеивания.
12. законы коммутативности (переместительности):

– коммутативность конъюнкции;

– коммутативность дизъюнкции.

1. законы ассоциативности (сочетательности):

– ассоциативность конъюнкции;

– ассоциативность дизъюнкции.

1. законы дистрибутивности (распределительности):

– дистрибутивность конъюнкции относительно дизъюнкции;

– дистрибутивность дизъюнкции относительно конъюнкции.

1. ; – законы де Моргана.

Доказать эти равносильности можно, например, с помощью таблиц истинности.

Пример.

Докажем равносильность – закон де Моргана. При любых комбинациях значений, от которых зависят формулы X и Y, эти формулы принимают некоторые логические значения. Всего будет четыре способа распределения логических значений X и Y. Надо показать, что в каждом из этих случаев значения левой и правой части равносильности совпадают.

X	Y

Логические значения в последних двух столбцах совпадают, следовательно, закон де Моргана справедлив.

Имеют место равносильности, выражающие одни логические операции через другие.

Импликация выражается через:

1. – дизъюнкцию и отрицание;
2. – конъюнкцию и отрицание.

Эквиваленция выражается через:

1. – конъюнкцию и импликацию;
2. – конъюнкцию, дизъюнкцию и отрицание;
3. – конъюнкцию и отрицание.

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

Существует логическая операция, через которую можно выразить любую из пяти логических операций, которыми мы пользуемся: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Эта операция называется «штрих Шеффера», обозначается символом и определяется таблицей истинности

X	Y

Согласно таблице, имеем: ; .