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

Формула Х называется тождественно истинной (или тавтологией), если она превращается в истинное высказывание, то есть принимает значение 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

 

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








Дата добавления: 2015-08-11; просмотров: 4224;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.