42420

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

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

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

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

Русский

2013-10-29

83 KB

30 чел.

Практическое занятие №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  


 

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

38513. Особливості маловідхідної технології вторинної переробки рудних пісків у балці «Крута» ВГМК 427 KB
  Значення вторинної переробки досить значне. По-перше ресурси багатьох матеріалів на Землі обмежені та не можуть бути заповнені в терміни, порівнянні з часом існування людської цивілізації. По-друге, потрапивши в навколишнє середовище, матеріали зазвичай стають забруднювачами.
38514. Описание технологического процесса изготовления детали «Муфта» 1019 KB
  Целью данной работы является: краткое описание характеристики цеха; описание оборудования приспособлений инструментов применяемых при изготовлении детали Муфта описание последовательности обработки детали Муфта назначение режимов резания при обработке детали составление технологической карты обработки; произвести обзор функций станков с ЧПУ описание программного обеспечения станков с ЧПУ тестирования и ввод коррекции станков с ЧПУ эксплуатации основных компонентов станков с ЧПУ методов наладки и контроля станка с ЧПУ...
38515. Цифрова обробка відеосигналу. Способи підключення відеопристроїв. mini-HDMI 5.02 MB
  Жорсткі диски того часу не перевершували обсягу одного CD а потужність процесора не дозволяла робити досить складних обчислень по розпакуванню звуку в реальному часі. Системи й методи цифрової обробки також розроблялися в оборонних галузях у першу чергу для рішення завдань радіолокації обробки гідроакустичних і телевізійних сигналів. Тому бажано щоб РКТ мав роз'єми DVI і HDMI 1. Види роз'ємів HDMI і кабелів Його досить часто можна зустріти на нових моделях комп'ютерів ноутбуків і телевізорів.
38516. Створення культурно розважального сайту міста Хмельницького 3.73 MB
  Виходячи з даних проблем у роботі даного вебсайту має бути розроблений сайт про культурно розважальне життя міста Хмельницького з усіма його подіями розважальними закладами та коротким описом. В ході дипломногопроетування було створено вебсай за допомогою якого користувачі можуть переглядати різні заклади для відпочинку а також різноманітні розважальні заходи що відбудуться у цих закладах чи інші події у місті Хмельницькому 1 Характеристика предметної області. Розглянемо похожі вебсайти на наявність переваг та недоліків.
38517. Раскрытие юридического механизма действия уголовно-правовой нормы об убийстве, совершенном при превышении пределов необходимой обороны 467 KB
  Равно как и тесно связанный с ним являющийся как бы его частью институт превышения пределов необходимой обороны.37 УК РФ не является преступлением причинение вреда посягающему лицу при защите личности и прав обороняющегося или других лиц интересов общества или государства от общественно опасного посягательства если при этом не допущено превышения пределов необходимой обороны. Стало быть превышение пределов необходимой обороны действие преступное.
38518. Общие сведения работы на предприятии, санитарно-технические требования и пошаговое приготовление блюд (Борщ и куриные котлеты на косточке) 845 KB
  Исторически борщ — это национальное блюдо Древнего Рима, где специально для него выращивали много капусты и свеклы. Из Рима этот прекрасный суп постепенно проник в кулинарии многих народов мира, в каждой из них приобретая свои особенные национальные черты.
38519. Разработка базы данных «Кредитование клиентов» 430 KB
  Одной из постоянных проблем персональных компьютеров является нехватка памяти. Как правило, персональный компьютер мы используем в ежедневной работе, учебе, отдыхе, играх. Поэтому очень важно, чтобы ваш ПК имел достаточное количество памяти для хранения различного рода информации
38520. Разработка дизайн-проекта актового зала ГБОУ СПО (ССУЗ) «Златоустовский Металлургический колледж» а с учетом эргономических требований 20.98 MB
  Сначала роль электрической лампочки выполняли обычные свечи рисунок 1 позже им на смену пришел керосин рисунок 2 потом появились газовые фонари рисунок 3. Рисунок 1 Свеча Рисунок 2 Керосиновая лампа Рисунок 3 Газовый фонарь Кованые фонари издавна использовались не только как средство освещения улицы или помещения но и как красивое украшение. Рисунок 4 Кованый фонарь Рисунок 5 Кованые фонари Рисунок 6 ...