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  


 

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

37891. Определение отношения теплоемкостей газа при постоянном давлении и объеме 1.41 MB
  11 Лабораторная работа № 116 Определение отношения теплоемкостей газа при постоянном давлении и объеме Цель работы Изучение закономерностей изменения параметров состояния газа в различных процессах и определение отношения теплоемкостей воздуха при постоянном давлении и объеме. Удельная и молярная теплоемкости газов зависят как от природы газа так и от условий его нагревания.3 Изменение внутренней энергии идеального газа однозначно определяется его начальным и конечным состояниями тогда как совершаемая газом работа зависит от характера...
37892. Определение отношения теплоемкостей газа при постоянном давлении и постоянном объеме резонансным методом 1.34 MB
  12 Лабораторная работа № 119 Определение отношения теплоемкостей газа при постоянном давлении и постоянном объеме резонансным методом 1. Теплоемкость и коэффициент Пуассона газа Для характеристики тепловых свойств вещества наряду с другими величинами используют молярную и удельную теплоемкости. Теплоемкость газа зависит от природы его молекул и от того как происходит его нагревание.1 Внутренняя энергия идеального газа это энергия теплового движения его молекул и атомов в молекулах.
37893. ОПРЕДЕЛЕНИЕ ТЕПЛОТЫ ПАРООБРАЗОВАНИЯ ВОДЫ 115 KB
  12 ЛАБОРАТОРНАЯ РАБОТА № 122 ОПРЕДЕЛЕНИЕ ТЕПЛОТЫ ПАРООБРАЗОВАНИЯ ВОДЫ Цель работы Определение удельной и молярной теплоты парообразования воды при фазовом переходе первого рода по экспериментально полученной зависимости давления насыщенных паров от температуры.11 Полученная формула устанавливает связь между молярной теплотой парообразования воды давлением и температурой водяного пара. Изменяя температуру пара T необходимо построить график зависимости по угловому коэффициенту которого можно определить молярную теплоту парообразования...
37894. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ ВОЗДУХА КАПИЛЛЯРНЫМ МЕТОДОМ 2.7 MB
  Изучение внутреннего трения воздуха как одного из явлений переноса в газах. При протекании жидкости или газа в узкой прямолинейной цилиндрической трубе капилляре при малых скоростях потока течение является ламинарным т. поток газа движется отдельными слоями которые не смешиваются между собой. Для идеального газа  υТ  2.
37895. ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 140 KB
  10 ЛАБОРАТОРНАЯ РАБОТА № 124 ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 1. Цель работы Ознакомление с одним из методов определения молярной массы и плотности газа. Теоретическая часть Состояние некоторой массы газа определяется значениями трёх параметров: давлением P под которым находится газ его температурой T и объёмом V.1 представляет собой уравнение состояния данной массы газа.
37896. ОПРЕДЕЛЕНИЕ ТЕПЛОЁМКОСТИ ТВЁРДЫХ ТЕЛ 440.5 KB
  Если температура калориметра с исследуемым образцом очень медленно увеличивать от начальной T0 на ∆T то энергия электрического тока пойдет на нагревание образца калориметра: 2.18 где I и U ток и напряжение нагревателя τ время нагревания m0 и m массы калориметра и исследуемого образца c0 c удельные теплоёмкости калориметра и исследуемого образца ∆Q потери тепла в теплоизоляцию калориметра и в окружающее пространство.18 количества теплоты расходованной на нагрев калориметра и потери теплоты в окружающее...
37897. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ТЕПЛОПРОВОДНОСТИ ГАЗА МЕТОДОМ НАГРЕТОЙ НИТИ 268.5 KB
  12 ЛАБОРАТОРНАЯ РАБОТА № 127 ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ТЕПЛОПРОВОДНОСТИ ГАЗА МЕТОДОМ НАГРЕТОЙ НИТИ Цель работы Изучение теплопроводности в газах и определение коэффициента теплопроводности воздуха. В твердых телах распространение тепла может происходить как путем теплопроводности так и путем конвекции или того и другого способа одновременно. Основным законом теплопроводности является закон Фурье который в одномерном случае распространения тепла в одном направлении пусть вдоль оси х имеет вид:...
37898. ИЗУЧЕНИЕ ПРИНЦИПА РАБОТЫ ТУННЕЛЬНОГО ДИОДА 3.81 MB
  Если полная энергия частицы Е U0 то с классической точки зрения частица может двигаться либо в области I где х 0 либо в области III где х d. Частица полная энергия которой меньше высоты потенциального барьера U0 не может с классической точки зрения перейти барьер из области I в область III. Волновая функция в этом случае отлична от нуля и в области II даже при значениях Е U0.1 для области II...
37899. Исследование космического излучения 1.03 MB
  Изучение поглощения космического излучения в свинце9 3. Изучение углового распределения интенсивности космического излучения.12 Лабораторная работа № 88 Исследование космического излучения 1. Цель работы 1 изучение зависимости интенсивности космического излучения от толщины пройденных им свинцовых пластин; 2 проверка феноменологической формулы зависимости интенсивности космического излучения от угла наблюдения.