Автор работы: Пользователь скрыл имя, 15 Января 2014 в 08:16, контрольная работа
Составление таблиц истинности формул, СДНФ, СКНФ, ДНФ, КНФ.
Составить таблицы истинности формул
(x ↔ӯ)˅(у↓x), ((x→ӯ)|z) ⊕ xy
Оглавление
Задание 1 3
Задание 2 3
Задание 3 4
Задание 4 5
Задание 5 6
Составить таблицы истинности формул
(x ↔ӯ)˅(у↓x), ((x→ӯ)|z) ⊕ xy
Таблица 1
x |
y |
x↔¬y |
y↓x |
˅ |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
Таблица 2
x |
y |
z |
x→¬y |
|¬z |
¬(xy) |
⊕ |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Проверить двумя способами, будут ли эквивалентны следующие формулы
x(y⊕z), xy⊕xz
А) составление таблиц истинности;
Таблица 3
x |
y |
z |
y⊕z |
x^ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
Таблица 4
x |
y |
z |
x^y |
x^z |
⊕ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Результирующие столбцы совпадают, формулы эквивалентны.
Б) приведение формул в СДНФ или СКНФ с помощью эквивалентных преобразований .
СДНФ: 1) xyz˅xyz
2) xyz ˅ xyz.
С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
(x˅ ӯ)→(z↔x)
Таблица 5
x |
y |
z |
x˅¬y |
¬(z↔¬x) |
→ |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
СДНФ:xyz˅xyz˅xyz ˅xyz˅ xyz получаем выписыванием строк, где функция принимает значение 1, там где аргумент равен 0 указываем инверсию.
СКНФ:(х˅y˅z)(x˅y˅z)(x˅y˅z) выписываем строки, где функция принимает значение нуля, там где аргументы функции равны единице записываем инверсное значение.
ДНФ: xz ˅ xz ˅ yz
КНФ: xz ˅ xz ˅ yz = (x˅z)(x˅y˅z) (x˅y˅z)
Пусть полином Жегалкина имеет вид:
P(x, y, z) = a0 ⊕ a1x ⊕ a2y ⊕ a3z ⊕ a12xy ⊕ a13xz ⊕ a23yz ⊕ a123xyz
P(0, 0, 0) = a0 = 1 => a0 = 1
P(0, 0, 1) = a0 ⊕ a3 = 0 => 1 ⊕ a3 = 0 => a3 = 1
P(0, 1, 0) = a0 ⊕ a2 = 1 => 1 ⊕ a2 = 1 => a2 = 0
P(0, 1, 1) = a0 ⊕ a2 ⊕ a3 ⊕ a23 = 1 => 1 ⊕ 0 ⊕ 1 ⊕ a23 = 1 =>
0 ⊕ a23 = 1 => a23 = 1
P(1, 0, 0) = a0 ⊕ a1 = 0 => 1 ⊕ a1 = 0 => a1 = 1
P(1, 0, 1) = a0 ⊕ a1 ⊕ a3 ⊕ a13 = 1 => 1 ⊕ 1 ⊕ 1 ⊕ a13 = 1 =>
1 ⊕ a13 = 1 => a13 = 0
P(1, 1, 0) = a0 ⊕ a1 ⊕ a2 ⊕ a12 = 0 => 1 ⊕ 1 ⊕ 0 ⊕ a12 = 0 =>
0 ⊕ a12 = 0 => a12 = 0
P(1, 1, 1) = а0 ⊕ а1 ⊕ а2 ⊕ а3 ⊕ а12 ⊕ а13 ⊕ а23 ⊕ а123 = 1 =>
1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ а123 = 1 => 0 ⊕ а123 = 1 => а123 = 1
Получаем полином Жегалкина:
P(x, y, z) = 1 ⊕ z ⊕ yz ⊕ x ⊕ xyz
Найдите сокращенную ДНФ булевой функции f(x, y, z) двумя способами:
f(0,0,1)=f(1,1,1)=f(1,1,0)=0
СКНФ: (x˅y˅z)(x˅y˅z)(x˅y˅z)
СДНФ: xyz˅xyz˅xyz˅xyz˅xyz
А) метод Квайна ;
После склеивания 1 с 4, 2 с 3 и 4 с 5 выражений в СДНФ получаем
xy ˅ yz ˅ xy
Б) с помощью карт Карно.
После сворачивания карты получаем xy ˅ yz ˅ xy
x\yz |
00 |
01 |
11 |
10 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
Каким классам Поста принадлежит эта форма?
Функция принадлежит к классу M (монотонная).
Является ли полной система функций? Образует ли она базис?
£={x⊕y, x˅y}
x˅y- функция сохраняет единицу
x⊕y- функция сохраняет ноль
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов T0, T1, S, M, L. Следовательно наша система неполная и образует базис {˅,⊕, ¬ }.