Задачи по дискретной математике. Баранов И.В - 13 стр.

UptoLike

ВУЗ: 

ДГТУ | Ростов-на-Дону

Составители: 

Рубрика: 

13
0 0 0 1 0 1
0 1 1 0 0 1
1 0 1 1 1 0
1 1 1 0 0 1
Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают.
3.30. Для упрощения формулы используем правило исключения имплика-
ции:
AAAA
1212
→=∨
.
¬→ ∨ → = ∨ ∨∨= ∧ ∨∨=()()() ()A A A A AA AA AA AA
12 21 1221
1
221
=∧∨∨=∧∨∨
=
∨() ()AA A AA A AA A
12 212 1 121
1
.
4.30. Используя законы логики приведем формулу ()AB C∧∨ к виду, содержащему
только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой
ДНФ:
() () ( ) ( )( )AB C AB C AB C AC B C∧∨=∧∧=∨∧=∧∨∧
Для построения СДНФ составим таблицу истинности для данной формулы:
A B C
A
∧B (A∧B)∨C
()AB C∧∨
0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 0 1 0
1 0 0 0 0 1
1 0 1 0 1 0
1 1 0 1 1 0
1 1 1 1 1 0
Помечаем те строки таблицы, в которых формула (последний столбец) принимает зна-
чение “1”. Для каждой такой строки выпишем формулу, истинную на наборе переменных
A,B,C данной строки: строка 1 –
A
B
C
∧
∧
; строка 3 –
A
B
C
∧
∧
; строка 5 –
A
B
C∧∧. Дизъюнкция этих трех формул будет принимать значение “1” только на набо-
0       0   0       1   0         1
0       1   1       0   0         1
1       0   1       1   1         0
1       1   1       0   0         1


        Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают.
        3.30. Для упрощения формулы используем правило исключения имплика-
ции: A1 → A2 = A1 ∨ A2 .

¬( A1 → A2 ) ∨ ( A2 → A1 ) = ( A1 ∨ A2 ) ∨ A2 ∨ A1 = ( A1 ∧ A2 ) ∨ A2 ∨ A1 =
= ( A1 ∧ A2 ) ∨ A2 ∨ A1 = A2 ∧ ( A1 ∨ 1) ∨ A1 = A2 ∨ A1 .
        4.30. Используя законы логики приведем формулу ( A ∧ B ) ∨ C к виду, содержащему
только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой
ДНФ:

( A ∧ B) ∨ C = ( A ∧ B) ∧ C = ( A ∨ B ) ∧ C = ( A ∧ C ) ∨ ( B ∧ C )
        Для построения СДНФ составим таблицу истинности для данной формулы:
    A       B      C        A∧B       (A∧B)∨C    ( A ∧ B) ∨ C
    0       0      0         0           0            1
    0       0      1         0           1            0
    0       1      0         0           0            1
    0       1      1         0           1            0
    1       0      0         0           0            1
    1       0      1         0           1            0
    1       1      0         1           1            0
    1       1      1         1           1            0
        Помечаем те строки таблицы, в которых формула (последний столбец) принимает зна-
чение “1”. Для каждой такой строки выпишем формулу, истинную на наборе переменных
A,B,C данной строки: строка 1 – A ∧ B ∧ C ; строка 3 – A ∧ B ∧ C ; строка 5 –
A ∧ B ∧ C . Дизъюнкция этих трех формул будет принимать значение “1” только на набо-




                                                13

Страницы