">
Математика Логика
Информация о работе

Тема: Законы логики Буля и логики высказывания

Описание: Упрощение выражения, воспользовавшись законами логики Буля. С помощью таблиц истинности сравнение выражения с исходным. Оценка выполнения преобразования. Аналитический путь. Справедливость. Аксиоматический, натуральный метод исчисления, резолюции и Вонга.
Предмет: Математика.
Дисциплина: Логика.
Тип: Курсовая работа
Дата: 27.08.2012 г.
Язык: Русский
Скачиваний: 13
Поднять уникальность

Похожие работы:

.

Курсовая работа по дискретной математике

Законы логики Буля и логики высказывания

2012 год.

Задание 1.

Максимально упростите выражение, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните упрощенное выражение с исходным.

Решение:



Преобразования:

По дистрибутивному закону 

По закону поглощения 

По закону противоречия 

По закону поглощения 

              0 0 0 0 0 0 0 0 1 1 1  1 0 0 0 1 0 0 0 1 1 1  0 1 0 0 1 0 0 0 1 1 1  1 1 0 0 1 0 0 0 1 1 1  0 0 1 0 0 0 0 0 1 1 1  1 0 1 0 1 0 0 0 1 1 1  0 1 1 0 1 0 0 0 1 1 1  1 1 1 0 1 0 0 0 0 0 0  0 0 0 1 0 0 0 0 0 0 0  1 0 0 1 1 0 0 0 1 1 1  0 1 0 1 1 0 0 0 1 1 1  1 1 0 1 1 0 0 0 1 1 1  0 0 1 1 0 1 0 1 1 1 1  1 0 1 1 1 1 1 0 1 1 1  0 1 1 1 1 0 0 0 1 1 1  1 1 1 1 1 0 0 0 1 1 1  

Следственно, преобразование выполнено, верно!

Задание 2:

Докажите аналитическим путем справедливость выражения







 – по этому закону все «+» раскрыты



Таким образом, видим, что конституэнты единицы левой части состоят из 3-х множеств, два из которых совпадают с конституэнтами выражения правой части.

Таким образом, можем сделать вывод, что правая часть выражения включает в себя левую часть, т.е. множество правой части включает множество левой.

Задание 3.

Представить заштрихованные и не заштрихованные области аналитическими выражениями

Разобьем заштрихованные части на отдельные области:

2) 3)

  

4) 5)

 

Объединим 1, 4, 5:



Разобьем не заштрихованную область на отдельные части:

2) 3)

 



Объединим области: 

Иначе заштрихованная область: 



Минимизация: каждая клетка с «1» соответствует конституэнте. По закону склеивания смежные конституэнты объединяют для получения импликанты . Все конституэнты заштрихованной области записаны сюда, потом 4 склеены в      

  1          

  

 1 1      1 1       

    

          0 0 0 0 0 0 1 0 0  1 0 0 0 1 1 0 0 0  0 1 0 0 0 0 1 1 1  1 1 0 0 0 0 0 0 0  0 0 1 0 0 0 1 0 0  1 0 1 0 1 1 1 0 0  0 1 1 0 0 0 1 1 1  1 1 1 0 0 0 1 1 1  0 0 0 1 0 0 1 0 0  1 0 0 1 1 1 0 0 0  0 1 0 1 0 0 1 1 1  1 1 0 1 0 0 0 0 0  0 0 1 1 0 0 1 0 0  1 0 1 1 1 1 1 0 0  0 1 1 1 0 0 1 1 1  1 1 1 1 0 0 1 1 1  

Задание 4

Клаузу необходимо доказать следующими методами: аксиоматическим, натурального исчисления, резолюции и Вонга.



Метод натурального исчисления:

 (1, уравнение эквивалентности, УЭ)

 (1, базовое правило, БП)

 (2, УЭ)

 (3, правило введения конъюнкции, ВК)

 (1, БП)

 (5, УЭ)

 (6, ВК)

 (4, удаление конъюнкции, УК)

 (4, УК)

 (удаление импликации, УИ)

 (10, УИ)

 (ВК)

 Следственно клауза не верна

Аксиоматичный метод:



Подставим в выражение, получим



Воспользуемся законом дистрибутивности, заменим «,» на «»





Метод Вонга

Доказательство сводится к последовательному разбиению дизъюнктов или конъюнктов, чтобы прийти к виду 

(





 не удовлетворяет клаузе Вонга

 не удовлетворяет клаузе Вонга

 

 

  не удовлетворяет клаузе Вонга

 не удовлетворяет клаузе Вонга





 не удовлетворяет клаузе Вонга

 не удовлетворяет клаузе Вонга

 

 

  не удовлетворяет клаузе Вонга

 не удовлетворяет клаузе Вонга, так как не смогли представить в виде 

Следственно, клауза не верна!

Метод резолюции

,    

  

1 2 3 4 5 6 7









Задание 5.

Ниже приведена легенда. Записать клаузу, отвечающую тексту или контексту легенды, с использование 4-6 различных букв. С помощью таблицы истинности найдите МНФ, минимальное и транверсальные покрытия.

Есть материалы

Есть станок

Изготовить партию фальшивых денег

Милиция хорошо работает

Высокая заработная плата милиционера

Высокая сознательность

Посылки:

Если будут и материалы и станок, то преступник изготовит партию фальшивых денег



Если хорошо работает милиция, то фальшивых денег не появиться 

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



Заключение:

Пока высокой зарплаты нет, но есть высокая сознательность милиции и нет преступлений

)

Клауза:



Таблица истинности n A B C D E F  P1 P2 P3 P P4  0 0 0 0 0 0 0 0 1 1 1 1 1  1 1 0 0 0 0 0 0 1 1 1 1 1  2 0 1 0 0 0 0 0 1 1 1 1 1  3 1 1 0 0 0 0 1 0 1 1 0 1  4 0 0 1 0 0 0 0 1 1 1 1 1  5 1 0 1 0 0 0 0 1 1 1 1 1  6 0 1 1 0 0 0 0 1 1 1 1 1  7 1 1 1 0 0 0 1 1 1 1 1 1  8 0 0 0 1 0 0 0 1 1 0 0 1  9 1 0 0 1 0 0 0 1 1 0 0 1  10 0 1 0 1 0 0 0 1 1 0 0 1  11 1 1 0 1 0 0 1 0 1 0 0 1  12 0 0 1 1 0 0 0 1 0 0 0 1  13 1 0 1 1 0 0 0 1 0 0 0 1  14 0 1 1 1 0 0 0 1 0 0 0 1  15 1 1 1 1 0 0 1 1 0 0 0 1  16 0 0 0 0 1 0 0 1 1 0 0 1  17 1 0 0 0 1 0 0 1 1 0 0 1  18 0 1 0 0 1 0 0 1 1 0 0 1  19 1 1 0 0 1 0 1 0 1 0 0 1  20 0 0 1 0 1 0 0 1 1 0 0 0  21 1 0 1 0 1 0 0 1 1 0 0 0  22 0 1 1 0 1 0 0 1 1 0 0 0  23 1 1 1 0 1 0 1 1 1 0 0 0  24 0 0 0 1 1 0 0 1 1 1 1 1  25 1 0 0 1 1 0 0 1 1 1 1 1  26 0 1 0 1 1 0 0 1 1 1 1 1  27 1 1 0 1 1 0 1 0 1 1 0 1  28 0 0 1 1 1 0 0 1 0 1 0 0  29 1 0 1 1 1 0 0 1 0 1 0 0  30 0 1 1 1 1 0 0 1 0 1 0 0  31 1 1 1 1 1 0 1 1 0 1 0 0  32 0 0 0 0 0 1 0 1 1 1 1 1  33 1 0 0 0 0 1 0 1 1 1 1 1  34 0 1 0 0 0 1 0 1 1 1 1 1  35 1 1 0 0 0 1 1 0 1 1 0 1  36 0 0 1 0 0 1 0 1 1 1 1 1  37 1 0 1 0 0 1 0 1 1 1 1 1  38 0 1 1 0 0 1 0 1 1 1 1 1  39 1 1 1 0 0 1 1 1 1 1 1 1  40 0 0 0 1 0 1 0 1 1 0 0 1  41 1 0 0 1 0 1 0 1 1 0 0 1  42 0 1 0 1 0 1 0 1 1 0 0 1  43 1 1 0 1 0 1 1 0 1 0 0 1  44 0 0 1 1 0 1 0 1 0 0 0 1  45 1 0 1 1 0 1 0 1 0 0 0 1  46 0 1 1 1 0 1 0 1 0 0 0 1  47 1 1 1 1 0 1 1 1 0 0 0 1  48 0 0 0 0 1 1 0 1 1 0 0 1  49 1 0 0 0 1 1 0 1 1 0 0 1  50 0 1 0 0 1 1 0 1 1 0 0 1  51 1 1 0 0 1 1 1 0 1 0 0 1  52 0 0 1 0 1 1 0 1 1 0 0 1  53 1 0 1 0 1 1 0 1 1 0 0 1  54 0 1 1 0 1 1 0 1 1 0 0 1  55 1 1 1 0 1 1 1 1 1 0 0 1  56 0 0 0 1 1 1 0 1 1 1 1 1  57 1 0 0 1 1 1 0 1 1 1 1 1  58 0 1 0 1 1 1 0 1 1 1 1 1  59 1 1 0 1 1 1 1 0 1 1 0 1  60 0 0 1 1 1 1 0 1 0 1 0 1  61 1 0 1 1 1 1 0 1 0 1 0 1  62 0 1 1 1 1 1 0 1 0 1 0 1  63 1 1 1 1 1 1 1 1 0 1 0 1  

СДНТ: 





Это конституанта истинного предиката , т.е. где «1» в столбике Р записывается соответственно ABCDEF, если 0 – то  , если 1- то А

МНФ: букв, кот. есть в каждой СДНТ – нет, следовательно МНФ = 

Минимальное покрытие: покрытие с наименьшим числом термов 

Трансверсальное покрытие включает все имеющиеся термы: