Дискретная математика

Автор: Пользователь скрыл имя, 10 Августа 2012 в 13:52, контрольная работа

Описание работы

Элементы математической логики. Основные понятия логики высказываний. Высказывание, основные логические операции. Логические переменные и формулы. Таблицы истинности логических операций и формул. Соглашение о приоритетах логических операций. и т.д.

Работа содержит 1 файл

Дискретная матАлматы.КР2 Вар.14.doc

— 324.00 Кб (Скачать)


.

1.14 Составить таблицы истинности для  формул:

A  →(BC)(A  → B) (A  → C)

Решение.        

Логические операции и их таблицы истинности

1. Конъюнкция – (), читается «x и y»

2. Дизъюнкция – ( ), читается «x или y».

3. Отрицание (инверсия) – (), читается «не x».

4. Импликация  -  (), читается «если х, то у».

5. Эквиваленция – (), читается «х если и только если у».

6. Штрих Шеффера – (), определяется как отрицание конъюнкции, т.е. читается «не x и y».

7. Стрелка Пирса – (), определяется как отрицание дизъюнкции, т.е. читается «не x или y».

8. Кольцевая сумма – (), определяется как отрицание эквиваленции (исключающее «или»), т.е. читается «или х, или у».

 

Вычисление значений логических выражений выполняется в определенном порядке, согласно их приоритету:

- Отрицание (инверсия)

- конъюнкция

- дизъюнкция

- импликация и эквивалентность

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Порядок действий в нашем примере:

1)     BC

2)     A  → B

3)     A  → C

4)     (A → B) (A  → C)

5)     A →(BC)

6)     A  →(BC)(A  → B) (A  → C)

Таблица истинности

0

0

1

0

0

1

1

1

1

0

0

1

 

0

1

1

0

1

0

1

1

0

0

0

1

0

0

1

0

1

1

1

 

1

1

1

1

0

0

0

Составим таблицу истинности для нашей формулы:

A

B

C

BC

A →B

A→C

(A→B) (A→C)

A →(BC)

Ф

0

0

0

0

1

1

1

1

1

0

0

1

1

1

1

1

1

1

0

1

0

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

0

1

1

0

1

1

1

1

1

1

0

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

Т.е. правая часть выражения эквивалентна левой.

2.14  Установить эквивалентность формул:

а) с помощью таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

x(yz) и (xy)(xz)

a) Составим таблицу истинности для нашей формулы:

 

x

y

z

yz

Ф1= x(yz)

xy

xz

(xy)(xz)

Ф2

0

0

0

0

1

1

1

0

1

0

0

1

1

1

1

1

0

1

0

1

0

1

1

1

1

0

1

0

1

1

0

1

1

1

0

1

1

0

0

0

1

1

1

0

1

1

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

0

1

0

0

0

1

Столбцы значений формул Ф1 и Ф2 совпадают, следовательно эти формулы эквивалентны.

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

 

Преобразуем выражение Ф1= x(yz)

По эквивалентному соотношению (16):

yz==d

По эквивалентному соотношению (15):

(использован закон Де-Моргана)

x(yz)= (с учетом двойного отрицания)

Используя дистрибутивность , получим:

x(yz)= - КНФ

Ф1= - СКНФ

 

Преобразуем теперь выражение Ф2=(xy)(xz):

t=(xy)= ; v=(xz)=;

(xy)(xz)=tv=

Ф2=(с учетом двойного отрицания)

; ; t==; v==;

Ф2=

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

=

Аналогично:

=

Ф2= (использовали свойство коммутативности)

Ф2  - СКНФ

Форма СКНФ(Ф1)= СКНФ(Ф2)

 


3.14 Упростить формулы: Ф=(A1A2) (A2A3) (A3A1)

Таблица истинности

0

0

0

1

0

1

0

1

1

0

0

0

1

1

1

1

 

Таблица для заданной формулы.

A1

A2

A3

A1A2

A2A3

(A1A2) (A2A3)

A3A1

Ф

0

0

0

1

1

1

1

1

1

0

0

1

1

1

1

0

0

0

0

1

0

1

0

0

1

1

1

0

1

1

1

1

0

0

1

1

1

0

0

0

1

0

1

1

1

1

0

1

0

1

0

1

1

1

1

1

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

Информация о работе Дискретная математика