42420

Булева алгебра. Законы логики высказываний. Эквивалентные преобразования

Лабораторная работа

Математика и математический анализ

Законы логики высказываний. Теоретическая часть Всё множество формул логики высказываний с точки зрения их значения истинности разбивается на три класса: 1 тождественно истинные тавтология; 2 тождественно ложные противоречие; 3 нейтральные. Особое место в логике высказываний занимают законы логики тождественно истинные формулы тавтологии. Законы логики высказываний Закон тождества: А эквивалентно А.

Русский

2013-10-29

83 KB

31 чел.

Практическое занятие №7

Тема: Булева алгебра.

Законы логики высказываний. Эквивалентные преобразования.

Занятие рассчитано на 2 академических часа.

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

Теоретическая часть

Всё множество формул логики высказываний с точки зрения их значения истинности разбивается на три класса:

1) тождественно истинные (тавтология); 2) тождественно ложные (противоречие); 3) нейтральные.

Определение 1: Формула называется тождественно истинной, если она принимает значение «истина» при всех наборах значений входящих в неё переменных.

Определение 2: Формула называется тождественно ложной, если она принимает значение «ложь» при всех наборах значений входящих в неё переменных.

Пример: - всегда истинна,  - всегда ложна.

   

А







1

0

1

0

0

1

1

0


Определение 3: Формула называется нейтральной, если она при одних наборах значений входящих в неё переменных принимает значение «истина», а при других - «ложь».

Тождественно истинные и нейтральные формулы образуют множество выполнимых формул, а тождественно ложные - множество невыполнимых формул. Особое место в логике высказываний занимают законы логики - тождественно истинные формулы (тавтологии).

Законы логики высказываний

  1.  Закон тождества: А эквивалентно А.
  2.  Закон противоречия: (неверно, что А и не А).
  3.  Закон исключенного третьего: А или не А
  4.  Коммутативный закон: , .
  5.  Ассоциативный закон: (С  С С  С.
  6.  Дистрибутивный закон: СС СС
  7.  Закон идемпотентности: , 
  8.  Закон поглощения:  
  9.  Закон исключения тавтологии из конъюнкции: .
  10.  Закон превращения дизъюнкции в тавтологию: 
  11.  Правило превращения конъюнкции в противоречие: 
  12.  Закон исключения противоречия из дизъюнкции: 
  13.  Закон двойного отрицания: 
  14.  Законы де Моргана:  
  15.  Закон склеивания:  
  16.  Законы выражения одних союзов через другие:

    =()() ;

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

Определение 4: Эквивалентным преобразованием данной формулы будем называть замену этой формулы через другую, которая ей эквивалентна.

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

Определение 5: Более простой по сравнению с данной формулой, не содержащей знаков импликации, двойной импликации, сильной дизъюнкции, отрицаний неэлементарных формул, будем считать формулу, которая содержит меньшее число: 1) вхождений букв; 2) знаков операций; 3) пар скобок.

Рассмотрим вопрос об упрощении системы высказываний.

Пусть F1, F2,…, Fn - какие-либо формулы логики высказываний. Они будут одновременно истинны только тогда, когда будет истинна их конъюнкция F1F2Fn.  Это даёт возможность упрощать системы высказываний. Для упрощения системы высказываний, каждое из которых истинно, необходимо:

  1.  записать каждое высказывание в такой эквивалентной форме, в которой исключены знаки импликации, двойной импликации и сильной дизъюнкции, а знаки отрицания отнесены только к атомам;
  2.  записать всю систему этих высказываний в виде конъюнкции;
  3.  применяя эквивалентные преобразования, упростить эту конъюнкцию.

Методические указания

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

Пример 1: Найти формулу эквивалентную данной, но с более простой структурой.

((CC(((C)(((CCCCCCCC=CCCCCC

Пример 2: Найти более простую дизъюнкцию, эквивалентную данной системе:

  1.  А 2) С 3)(ВС).

Решение: Из всех высказываний исключим знаки импликации:

1) 2) С 3) СС

Теперь составим их конъюнкцию:

(СССССС

Пример 3: Для заданной формулы АВ составьте таблицу истинности и интерпретируйте  на диаграммах Эйлера-Венна.

Решение: Связь между высказываниями и их множествами истинности дает возможность переводить любую задачу, относящуюся к сложным высказываниям, в задачу теории множеств. Возможно и обратное: если сформулирована задача относительно операции над множествами, то универсальное множество можно представить как некоторое множество логических возможностей, а его подмножества как множества истинности некоторых высказываний. Таким образом, каждому высказыванию соответствует множество истинности. Каждой операции над высказываниями соответствует операция над множествами. Каждому отношению соответствует отношение между множествами истинности.

В нашем случае, если А и В - высказывания, то, например, АВ - также высказывание, и следовательно, оно должно иметь свое множество истинности. Изобразим это множество. Значению истинности переменных А и В в каждой из четырех строк таблицы истинности ставим в соответствие одно из четырех подмножеств на диаграмме Эйлера-Венна (рис.1).

Строки

А

В

Подмножества

истинности

1

1

1

А1∩В1

2

1

0

А1∩ ┐В1

3

0

1

┐А1∩В1

4

1

1

┐А1∩┐В1

Рис 1.

 

Рис.2.

     

Подмножества, соответствующие тем строкам, в которых молекулярное высказывание истинно, заштриховываются. Таким образом, высказыванию АВ ставится в соответствие множество (А1∩┐В1)U(┐А1∩В1), ибо АВ истинно во 2 и 3 строках таблицы, т.е.={10,01}.

Контрольные вопросы

1. Дайте определение тождественно истинной, тождественно ложной и нейтральной формул.

2. В чем состоит проблема минимизации формул?

3. Что называется эквивалентным преобразованием формулы?

4. Перечислите все 15 законов логики высказываний.

5. Назовите законы выражения одних союзов через другие.

6. Как производится упрощение системы высказываний?

Индивидуальные задания

1. Определите, с помощью таблицы истинности, является ли приведенная функция тождественно-истинной, тождественно-ложной или нейтральной.

1) С 11) С    21)  

2) С|  12) С    22)  С

3) С 13) С         23)  С

4) С| 14) С     24)  С

5) С 15) С         25) 

6) С|С  16) С          26)  С 

7) СС 17)СС         27) СС

8) С  18) С       28) С

9)  19) С     29) С

10) С 20) С; 30) С

2.  Для заданной формулы составьте таблицу истинности и интерпретируйте  на диаграммах Эйлера-Венна.

1)   ССВ 11)АС      21) САС

  1.  АССВ 12) СС  22) С
  2.  ССС 13) В        23) АССВ
  3.  С   14) ССА     24) ССА
  4.  С 15) АСС25) АС
  5.  ССА 16) СА26) САС
  6.  АС 17) ВСА   27) СВС

8  СВС 18)ССС     28) С;

     9)  СС 19) СВ     29) ССС

    10) САС 20) ССВ;  30) С|СВ;

3.  Исследуйте,  подчинена ли операция:

1) импликации законам коммутативности, ассоциативности и идемпотентности, т.е. верно ли, что:

1) АВ=ВА; 2) (АВ)С=АС); 3) АА=А.

2) двойная импликация законам коммутативности, ассоциативности и идемпотентности, т.е. верно ли, что:

1) А↔В=В↔А; 2) (А↔В)↔С=А↔(В↔С); 3) А↔А=А.

3) строгая дизъюнкция (эквиваленция) законам коммутативности, ассоциативности и идемпотентности?

4) «штрих Шеффера» и «символ Лукасевича» законам коммутативности, ассоциативности и идемпотентности?

4.  Сформулируйте высказывания, которые по законам де Моргана, выражают то же, что и следующие:

1) Неверно, что треугольник АВС – прямоугольный и равнобедренный; 2) Неверно, что хотя бы одно из чисел а и в - простое;

3) Неверно, что число 9- четное или простое;

4) Неверно, что каждое из чисел m и n чётно.

PAGE  1


А
1       В1  U

     2

    3

  2  


 

А также другие работы, которые могут Вас заинтересовать

80762. Object of the Theory of Grammar. Its place among Other Linguistic Sciences 29.78 KB
  Language is social by nature: it is inseparably connected with the people who are its creators users. L. consists of three parts (sides): the phonological system, the lexical system, the grammatical system; without any one of them three is no human L. in the above sense.
80763. DISTINCTIVE LINGUISTIC FEATURES OF THE MAJOR FUNCTIONAL STYLES OF ENGLISH 26.76 KB
  A functional style of language is a system of interrilated language means which serve a definite in communication. The english literary standard we distinguish the following major functional styles: the language of belles-letters, the languge publicistic literaeture, the language of newspapers...
80764. Право граждан на благоприятную окружающую среду 31.86 KB
  Право на жизнь объединяет с правом на благоприятную окружающую среду то что первое несомненно связано с состоянием окружающей среды в которой проживает человек. По оценкам Всемирной организации здравоохранения состояние здоровья человека до 80 определяется условиями среды его обитания. Есть основания предположить что годы жизни укорочены наряду с другими причинами изза деградации окружающей среды. В той части в какой право на жизнь связано с охраной природной среды оно может защищаться способами и средствами предусмотренными...
80765. Право на достоверную информацию о состоянии окружающую среду. Источники экологической информации 33.31 KB
  Источники экологической информации. ФЗ Об информации информационных технологиях и защите информации предусматривает защиту прав граждан на экологическую информацию в том числе сведения о последствиях аварий и катастроф информацию о безопасности населенных пунктов. Подобная информация не может составлять государственную тайну доступ к данной информации не может быть ограничен. Одним из критериев такой информации является ее достоверность.
80766. Права общественных формирований в области охраны окружающей среды 31.04 KB
  Полномочия общественных экологических объединений в области охраны окружающей природной среды предусмотрены рядом законодательных актов. Федерального закона Об охране окружающей среды. Одним из примеров реализации прав общественных объединений в области охраны окружающей среды может служить опротестование Российским социально-экологическим союзом в Вологодском областном арбитражном суде решения вологодских властей о строительстве на территории Национального природно-исторического парка Русский Север образованного Правительством РФ в...
80767. Право собственности на природные объекты: понятие, виды, объекты и субъекты, основания возникновения 30.39 KB
  Земля и другие природные ресурсы могут находиться в частной государственной муниципальной и иных формах собственности. Земли которые не находятся в собственности граждан юридических лиц или муниципальных образований представляют собой государственную собственность. Право собственности на природные ресурсы возможность владения пользования и распоряжения данными природными ресурсами.
80768. Право природопользования: понятие, содержание и виды 35.24 KB
  Позитивное природопользование классифицируется по объекту природопользования на землепользование водопользование пользование лесами недрами и животным миром. Право природопользования понимается в двух значениях. В объективном смысле право природопользования это совокупность правовых норм регулирующих отношения по поводу использования и охраны природных ресурсов.
80769. Право общего природопользования 34.47 KB
  При этом однако в ряде случаев устанавливаются пределы и условия общего пользования природными ресурсами. Однако в составе земель поселений выделяются рекреационные территориальные зоны на которых осуществляется право общего землепользования. Землями общего пользования в значительной степени являются земли лесного фонда правовой режим которых определяется земельным законодательством.
80770. Право специального природопользования: основания возникновения и прекращения 31.45 KB
  Формы специального природопользования: комплексное природопользование; специальное пользование водами недрами объектами животного мира другими природными ресурсами. Необходимость введения комплексного природопользования обусловлена тем что нередко при предоставлении одного природного ресурса в пользование используются в большей или меньшей степени другие ресурсы либо на них оказывается воздействие. Право специального природопользования возникает на основании разрешений лицензий договоров оформляемых в рамках определенных в...