1). Упростите заданные логические формулы и проверьте равносильность исходной и упрощенной формул с помощью их таблиц истинности (знак логического умножения (конъюнкции) в записи формул опускается).
2). Для логической функции, соответствующей полученным формулам, напишите СДНФ и СКНФ и упростите их с помощью карт Карно.
Вариант №1
а)
б)
Вариант №2
а)
б)
Нужно полное решение этой работы?
Решение
Вариант №1
1). а)
ABC∨ABC∨ABC∨ABC∨ABC=ABC∨ABC∨ABC∨ABC∨ABC∨ABC∨ABC∨ ABC∨
∨ABC∨ABC=AB∨AC∨BC∨AC∨AB=AB∨AC∨AC∨AB∨BC=AB∨C∨C∨B∨BC=
=A1∨BC=A∨BC
A
B
C
A
B
C
ABC
ABC
ABC
ABC
ABC
1). а) A∨BC
0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 1 1 1
1 0 0 0 1 1 0 0 0 1 0 1 1
1 0 1 0 1 0 0 0 1 0 0 1 1
1 1 0 0 0 1 0 1 0 0 0 1 1
1 1 1 0 0 0 1 0 0 0 0 1 1
б)
B∨AB→AB→B∨A⇔BA→B=B∨AB∨AB∨B∨A⇔BA∨B=
=BAB∨A∨B∨B∨A⇔BA∨B=BA∨B∨1⇔BA∨B=B∨1→BB→1A∨B=
=B∨1∨BB∨1A∨B=B∨0∨B1A∨B=B∨BA∨B=B∨B=1, т.е. путём равносильных преобразований получили, что исходная формула — тавтология. Построим её сокращённую таблицу истинности (в ней конъюнкцию будем указывать явно).
(B
∨
(A
∧
B)) →
((((A
∧
B) →
(B
∨
A)) ⇔
B) ∧
(A
→
B))
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0
1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1
0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2). а) Заметим, что исходная формула — уже СДНФ
A
B
C
формула дизъюнкт конъюнкт
0 0 0 0 A∨B∨C
0 0 1 0 A∨B∨C
0 1 0 0 A∨B∨C
0 1 1 1
ABC
1 0 0 1
ABC
1 0 1 1
ABC
1 1 0 1
ABC
1 1 1 1
ABC
СКНФ — A∨B∨CA∨B∨CA∨B∨C;
СДНФ — ABC∨ABC∨ABC∨ABC∨ABC.
Строим карту Карно:
B C
00 01 11 10
A 0 0 0 1 0
1 1 1 1 1
Минимизируем СКНФ:
1
1
Данная СКНФ имеет единственную тупиковую КНФ, поэтому и минимальная КНФ единственная — A∨BA∨C.
Минимизируем СДНФ:
1
1
Данная СДНФ имеет единственную тупиковую ДНФ, поэтому и минимальная ДНФ единственная — A∨BC.
б) Поскольку формула является тавтологией, то она не имеет СКНФ;
СДНФ — ABC∨ABC∨ABC∨ABC∨ABC∨ABC∨ABC∨ABC
Строим карту Карно:
B C
00 01 11 10
A 0 1 1 1 1
1 1 1 1 1
Вся таблица представляет блок 2×4, все логические переменные в его границах меняют значения, поэтому МДНФ — 1.
Вариант №2
1)
. а)
A∨B∨CA∨B∨CA∨B∨CA∨B∨CA∨B∨C≡A∨CA∨BB∨CB∨CA∨C≡
≡A∨CA∨BB∨CB∨CA∨C≡A∨BC
A
B
C
A
B
C
A∨B∨C
A∨B∨C
A∨B∨C
A∨B∨C
A∨B∨C
1). а) A∨BC
0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 0 1 1 1 1 0 0
0 1 0 1 0 1 1 1 1 1 1 1 1
0 1 1 1 0 0 1 0 1 1 1 0 0
1 0 0 0 1 1 1 1 0 1 1 0 0
1 0 1 0 1 0 1 1 1 0 1 0 0
1 1 0 0 0 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 0 1 1 0 0 0
б)
AB⇔AC∨BA∨C→ABA∨B∨AC≡AB∨ACAB∨AC∨BA∨C∨ABA∨B∨AC≡
≡AB∨AC∨AB∨AC∨BAC∨ABA∨ABB∨ABAC≡ABAC∨ABAC∨BAC∨0∨0∨ABC≡
≡ABA∨C∨A∨BAC∨BAC∨ABC≡ABA∨C∨AAC∨BAC∨BAC∨BABC≡
≡ABA∨ABC∨0∨ABC∨ABC∨ABC≡0∨ABC∨ABC∨ABC≡ABC∨ABC∨ABC≡BC∨ABC
Построим сокращённую таблицу истинности (в ней конъюнкцию будем указывать явно).
(A
B
A
C) B
(A
C
A
B
(A
B
(A
C))
0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1
0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0
0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1
1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0
0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0
1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1
(B
C) (A
B
C)
0 0 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1
1 1 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 1
0 0 1 0 1 1 1 0 0
1 0 0 0 1 0 0 0 1
1 1 1 1 1 0 0 0 0
2)