Алгебра высказываний

АЛГЕБРА ВЫСКАЗЫВАНИЙ

§1. Формализация высказываний

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

 

17. Если он хочет достигнуть цели, он должен много знать и быть удачливым.

Решение

Пусть А=  " Он хочет достигнуть цели ", В =  " он должен много знать ", С =  " он должен быть удачливым ". Тогда данное предложение символически можно записать в виде

.

Можно обойтись без скобок, можно поставить, чтобы подчеркнуть порядок действий:

§2. Таблицы истинности высказываний

Построить таблицы истинности для следующих высказываний.

17. ;

 

A	B	AB						F
0	0	0	1	1	0	1	1	1
0	1	0	1	1	1	0	1	1
1	0	0	1	1	0	1	0	1
1	1	1	0	1	1	0	0	0

 

Заполним столбец AB, пользуясь тем, что 0·0=0, 0·1=0, 1·0=0, 1·1=1. Заполним столбец таблицы, соответствующий , пользуясь тем, что =1, =0. Затем, на основе столбцов A и заполним столбец , пользуясь тем, что 0 1=1, 0 0=0, 1 1=1, 1 0=1. На основе столбцов B и заполним столбец , используя правило: 0 0=1, 0 1=0, 1 0=1, 1 1=1. Заполним столбец , причем будем ставить в некоторой строке 1, если в той же строке столбца стоит 0, и наоборот. Затем, на основе столбцов и заполним столбец F= , пользуясь тем, что 0 1=1, 0 0=0, 1 1=1, 1 0=1.

§3. Дизъюнктивные нормальные формы (ДНФ)

Привести данные высказывания к  ДНФ.

 

 

_17.

 

_{Решение:}

 

_{Получили  тождественно истинное высказывание. Можно  его записать в виде СДНФ:}

 

§4. Совершенные дизъюнктивные нормальные формы  
(СДНФ)

Привести данные высказывания к  СДНФ, по возможности упростить.

 

 

_17. ;

Решение

Построим таблицу истинности высказывания F.

 

A	С	D	AC
0	0	0	0	1	0	0	1
0	0	1	0	0	1	0	1
0	1	0	0	1	0	0	1
0	1	1	0	0	1	0	1
1	0	0	0	1	0	0	1
1	0	1	0	0	1	0	1
1	1	0	1	0	1	0	1
1	1	1	1	1	0	1	0

 

 

A	С	D	CD				F
0	0	0	0	0	0	1	0
0	0	1	0	0	1	0	0
0	1	0	0	0	0	1	0
0	1	1	1	0	1	0	0
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	0	0	1	0

 

F=A¹C⁰D⁰ A¹C⁰D¹ A¹C¹D⁰

Высказывание приведено  к СДНФ. Полученную СДНФ можно упростить, приведя ее к более простой ДНФ.

.

§5. Построение СДНФ для  высказываний,  
заданных таблицами истинности

Привести данные высказывания к СДНФ, по возможности упростить.

 

 

                 17.

 

a	b	c	F(a,b,c)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 0 0 0 0 0 0 0

 

В таблице всего в  одной строке (в итоговом столбце) стоит единица. Поэтому будет  всего один член: