Контрольная работа, логика высказываний ( вариант 5 )

22.03.2015, 09:06

Задача 1. Для функции, реализованной формулой построить таблицы истинности:
5. .

x y z
0 0 0 0 1 0 1 0 0 1
0 0 1 0 0 0 1 1 1 1
0 1 0 1 1 1 1 0 1 1
0 1 1 1 0 0 1 1 1 1
1 0 0 1 1 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0
1 1 0 0 1 1 0 0 1 1
1 1 1 0 0 0 0 0 0 1
Задача 2. Определить значение функции, которая реализована формулой, на наборах
(0, 0, 1), (1, 1, 0), (1, 1, 1):

Решение:

Построим таблицу истинности для данной функции:

a b c
0 0 0 1 1 0 1
0 0 1 1 1 0 1
0 1 0 0 0 1 1
0 1 1 0 0 0 1
1 0 0 0 1 0 1
1 0 1 0 1 0 1
1 1 0 0 0 1 1
1 1 1 0 0 0 1

F(0, 0, 1)=1
F(1, 1, 0)=1
F(1, 1, 1)=1.

полином Жегалкина ⌐((z→x)↔(y│x))

полином Жегалкина ⌐((z→x)↔(y│x));

[ Скачать с сервера (79.5Kb) ] 27.02.2012, 18:41
Построим полином Жегалкина: P=C0+C1X+C2Y+C3Z+C12XY+C13XZ+C23YZ+C123XYZ

 

используя таблицу истинности для формулы ⌐((z→x)↔(y│x));

x y z (z→x) (y│x) ((z→x)↔(y│x)) ⌐((zx)↔(yx))
1 1 1 1 0 0 1
1 1 0 1 0 0 1
1 0 1 1 1 1 0
1 0 0 1 1 1 0
0 1 1 0 1 0 1
0 1 0 1 1 1 0
0 0 1 0 1 0 1
0 0 0 1 1 1 0

 

Подстановка наборов значений переменных (x,y,z) – последовательностей нулей и единиц, приводит к следующим соотношениям для коэффициентов полинома:

 

F(0,0,0)= P(0,0,0)= C0=0

F(0,0,1)= P(0,0,1)= C0+C3 =1

F(0,1,0)= P(0,1,0)= C2+C0 =0

F(0,1,1)= P(0,1,1)= C23+C2+C3+C0=1

F(1,0,0)= P(1,0,0)= C1+C0=0

F(1,0,1)= P(1,0,1)= C13+C1+C3+C0=0

F(1,1,0)= P(1,1,0)= C12+C1+C2+C0=1

F(1,1,1)= P(1,1,1)= C123+C12+C13 +C23+C1+C2+C3+C0=1

 

Последовательно найдем коэффициенты:

C0=0, C1=0, C2=0,C3=1, C23=0, C13=1, C12=1,C123 =0

 

Подставив, получим, что полином Жегалкина имеет вид:

⌐((z→x)↔(y│x))= Z+XZ+XY
 

посмотреть еще задачи по дискретной математике

 

построить СКНФ и СДНФ исходной функции f=(x~y&z) + (┐x&y) V z, используя эквивалентные преобразования.

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

Решение:

 С помощью закона склеивания приведем к СДНФ:

(совершенной дизъюнктивной нормальной форме, или можно сказать составим дизъюнкцию конъюнкций)

Приведем упрощенную формулу к СКНФ

(совершенной конъюнктивной нормальной форме, или можно сказать к конъюнкции дизъюнкций)

P.S.:

можете сравнить результаты с нахождением СДНФ и СКНФ, с помощью таблицы истинности(функция та же)

 

посмотреть другие задачи по дискретной математике

Построить СКНФ и СДНФ исходной функции f=(x~y&z) + (┐x&y) V z, используя таблицу истинности

построить СКНФ и СДНФ исходной функции f=(x~y&z) + (┐x&y) V z, используя таблицу истинности

Решение:
построим таблицу истинности для функции

 x y z  y&z  x~y&z  x x&y   f
 0  0  0  0  1  1  0  1  1
 0  0  1  0  1  1  0  1  1
 0  1  0  0  1  1  1  0  0
 0  1  1  1  0  1  1  1  1
 1  0  0  0  0  0  0  0  0
 1  0  1  0  0  0  0  0  1
 1  1  0  0  0  0  0  0  0
 1  1  1  1  1  0  0  1  1

Исходя, из таблицы истинности

построим СКНФ функции:

Построим СДНФ функции

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

видно, что СКНФ и СДНФ совпали,значит найдены верно.

посмотреть другие задачи по дискретной математике

Найдите все интерпретации, в которых указанные формулы принимают одинаковые истинностные значения: P <-->R & ┐Q; (R↓Q)—>P

26.01.2012, 18:13

найдите все интерпретации, в которых указанные формулы принимают одинаковые истинностные значения:
P <—>R & ┐Q,  (R↓Q)—>P

Решение:
так как переменных три , то количество наборов будет 2^n=2^3=8

Построим таблицу истинности для трех переменных:

 P  R Q
┐Q
R&┐Q
P<—>R&┐Q
 (R↓Q) (R↓Q)—>P
 0  0  0  1  0  1  1  0
 0  0  1  0  0  1  0  1
 0  1  0  1  1  0  0  1
 0  1  1  0  0  1  0  1
 1  0  0  1  0  0  1  1
 1  0  1  0  0  0  0  1
 1  1  0  1  1  1  0  1
 1  1  1  0  0  0  0  1

Задача на минимизацию булевых функций от трех переменных

задача на минимизацию булевых функций от трех переменных
[ Скачать с сервера (152.5Kb) ] 24.01.2012, 18:12

е задание.
Записать формулу функции f(x1,x2,x3)  и минимизировать ее
графическим методом,
методом неопределенных коэффициентов,
методом минимизирующих карт Карно,
методом Квайна.
Для метода неопределенных коэффициентов вывести на экран полученную систему уравнений, ее решение, СДНФ и МДНФ.
Для метода минимизирующих карт вывести на экран последовательность минимизирующих карт, СДНФ и МДНФ.
Сравнить полученные результаты.
x1    x2    x3   f
0      0     0   1
0      0     1   1
0      1     0   0
0      1     1   1
1      0     0   0
1      0     1   1
1      1     0   0
1      1     1   1

Решение:
Графический метод минимизации функции:
Минимизация логических функций с помощью графического представления n-мерного куба.
При количестве переменных не более 4-х все возможные тупиковые и саму минимальную формы можно просто увидеть на пространственной диаграмме — n-мерном (в нашем примере — 3-х мерном) кубе — декартовом графике (рисунок), где на осях, соответствующих переменным, отображены точки их возможных состояний (0 или 1). Точки-состояния, в которых (согласно таблице истинности) функция принимает единичные значения, изобразим более крупными:
(у нас  точки (0,0,0), (0,0,1), (0,1,1), (1,0,1), (1,1,1))

Формула ребра вдоль оси-переменной не содержит этой переменной, т. к. значение функции на «склеенных» им вершинах не зависит от значения этой переменной, что соответствует операции выноса за скобки общего множителя.
Ребро ┐x •┐y соединяет точки ┐x•┐y•┐z и ┐x•┐y•z
:
( ┐x•┐y•┐z )+( ┐x•┐y•z) = ┐x•┐y •( ┐z + z) =┐x•┐y
А грань будет соответствовать z

По диаграмме задача минимизации сводится к объединению максимума вершин, на которых функция принимает единичные значения, в минимум ребер.
В нашем случае, минимальная ДНФ равна:
f(x,y,z)=(┐x•┐у)\/z

перейдем к исходным переменным х1,х2 и х3,
им соответствуют переменные x,y,z
МДНФ: f(x1,х2,х3)=(┐x1•┐x2)\/x3

Минимизация методом неопределенных коэффициентов:
Метод неопределенных коэффициентов.
Суть метода состоит в преобразовании ДСНФ в МДНФ.
На основании теоремы Жегалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов:
1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.
2. Напротив каждого выражения поставить соответствующее значение функции.
3. Выбрать строку, в которой значение функции  и приравнять все   к нулю.
4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.
5. Проанализировать оставшиеся коэффициенты в единичных строках.
6. Используя правило, что дизъюнкция равна 1 если хотя бы один из  , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.
7. Записать исходный вид функции.
Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

Представим функцию f(x1,x2,x3) в виде следующей
СДНФ:

Составляем схему:

0    0    0    0    00    00    00    000    1
1    0    0    1    00    01    01    001    1
2    0    1    0    01    00    10    010    0
3    0    1    1    01    01    11    011    1
4    1    0    0    10    10    00    100    0
5    1    0    1    10    11    01    101    1
6    1    1    0    11    10    10    110    0
7    1    1    1    11    11    11    111    1

Приравняем 0 в каждом уравнении все коэффициенты,
кроме тех, которые отвечают конъюнкциям,
которые содержат, наименьше число переменных:

Итак, получим МДНФ

Метод Квайна:

Составим СДНФ функции:

-сокращенная ДНФ

И построим матрицу Квайна

Матрица Квайна:

*    *

*    *    *    *

Выписываем
тупиковая ДНФ:
(для столбцов, где стоит одна *)
\/

Выбираем из тупиковых минимальную:  \/

Минимизация, с помощью карт Карно:
исходная функция зависит от трех переменных, таблицу истинности можно представить виде:
х2
х3

х1    0
0    0
1    1
1    1
0
0    000    001    011    010
1    100    101    111    110

Подставив значения функции, получим

х2
х3

x1
0
0
0
1    1
1    1
0
0    1    1    1    0
1    0    1    1    0

СДНФ функции состоит из пяти слагаемых:

Выписываем тупиковые ДНФ:
\/ .
Выбираем из тупиковых минимальную ДНФ:  \/ .
ВЫВОД:
Сравнивая МДНФ, полученную разными способами (графическим методом,
методом неопределенных коэффициентов, методом минимизирующих карт Карно, етодом Квайна. ) , видно, что МДНФ найдена верна, так как совпали результаты.

(ПОДРОБНОЕ И ЯСНОЕ РЕШЕНИЕ В ФАЙЛЕ, КОТОРЫЙ МОЖНО СКАЧАТЬ, пройдя регистрацию на сайте )

посмотреть другие задачи по дискретной математике

Метод Карт Вейча. Минимизация булевых функций от пяти переменных.

минимизация булевых функций от пяти переменных. метод Карт Вейча
[ Скачать с сервера (145.5Kb) ] 24.01.2012, 18:11

Записать формулу функции f(x1х2,х3,х4,х5) в виде СДНФ и минимизировать методом карт Вейча.
x1 x2  x3  x4  x5    f(x1х2,х3,х4,х5)
0    0    0    0    0
0    0    0    0    1    1
0    0    0    1    0
0    0    0    1    1
0    0    1    0    0    1
0    0    1    0    1
0    0    1    1    0
0    0    1    1    1
0    1    0    0    0
0    1    0    0    1    1
0    1    0    1    0    1
0    1    0    1    1    1
0    1    1    0    0
0    1    1    0    1
0    1    1    1    0
0    1    1    1    1    1
1    0    0    0    0    1
1    0    0    0    1
1    0    0    1    0
1    0    0    1    1
1    0    1    0    0
1    0    1    0    1    1
1    0    1    1    0    1
1    0    1    1    1    1
1    1    0    0    0    1
1    1    0    0    1
1    1    0    1    0
1    1    0    1    1
1    1    1    0    0
1    1    1    0    1    1
1    1    1    1    0    1
1    1    1    1    1    1
Запишем СДНФ функции

Перерисуем таблицу истинности в двухмерный вид:

х4
х5

х2х3    0
0    0
1    1
1    1
0    0
0    0
1    1
1    1
0
0  0    10000    10001    10011    10010    00000    00001    00011    00010
0  1    10100    10101    10111    10110    00100    00101    00111    00110
1  1    11100    11101    11111    11110    01100    01101    01111    01110
1  0    11000    11001    11011    11010    01000    01001    01011    01010

Подставив значения функции, получим

х4
х5

х2х3    0
0    0
1    1
1    1
0    0
0    0
1    1
1    1
0
0  0         1                            1
0  1             1         1        1         1
1  1             1         1        1                     1
1  0         1                         1         1         1

Минимизируем в соответствии с правилами:

х4
х5

х2х3    0
0    0
1    1
1    1
0    0
0    0
1    1
1    1
0
0  0         1                            1
0  1             1         1        1         1
1  1             1         1        1                     1
1  0         1                         1         1         1

1)   2)   3)   4)    5)
6)
7)
8)
9)
Сокращенная ДНФ:
=1) \/ 2) \/ 3) \/ 4) \/ 5) \/ 6) \/ 7) \/ 8) \/ 9) =
= ( )\/ ( ) \/ ( ) \/ ( ) \/ ( )\/
\/( )\/( )\/( )\/( )
Функция имеет несколько тупиковых  ДНФ:
=( )\/ ( )\/( )\/( )\/
\/( )\/( )
=( )\/ ( )\/( )\/( )\/
\/( )\/( )\/( )\/( )

Выбираем из всех тупиковых ДНФ минимальную ДНФ:  =( )\/ ( )\/( )\/( )\/( )\/( )

(ПОДРОБНОЕ И ЯСНОЕ РЕШЕНИЕ В ФАЙЛЕ, КОТОРЫЙ МОЖНО СКАЧАТЬ)

посмотреть другие задачи по дискретной математике

Являются ли функции эквивалентными

построив таблицу, выяснить, являются ли функции эквивалентными:

Решение:
Построим таблицу истинности для функции 


 

 x  y  z  x&y  y&z      u    
 0  0  0  0  0 1 0  0  1  1  0  1    
 0  0  1  0  0 1 0  0  1  1  1  0    
 0  1  0  0  0 1 0  1  0  0  1  0    
 0  1  1  0  1 1 1  1  0  0  1  1    
 1  0  0  0  0 0 1  1  1  1  0  0    
 1  0  1  0  0 0 1  1  1  1  1  1    
 1  1  0  1  0 0 1  1  0  1  0  0    
 1  1  1  1  1 0 1  1  0  1  1  1    

Построим таблицу истинности для функции 

 x y z      
0  0  0 1 0  1
 0  0  1  1  1  0
 0  1  0  1  1  0
 0  1  1  1  0  1
 1  0  0  0  0  0
 1  0  1  0  1  1
 1  1  0  1  1  0
1 1 1 1 0 1

Видим, что наборы переменных для данных функций совпали, следовательно, они эквивалентные.

посмотреть еще задачи по дискретной математике
 

Задача на нахождение ДНФ, КНФ, СДНФ, СКНф, полином Жегалкина

 

[ Скачать с сервера (163.5Kb) ]
С помощью эквивалентных преобразований приведите
формулу к ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина

⌐((z→x)↔(y│x));

Решение:

Приведем формулу ⌐((z→x)↔(y│x)) к ДНФ (дизъюнктивной нормальной
форме), то есть получим дизъюнкцию конъюнкций: ⌐((z→x)↔(y│x))

Избавимся от эквиваленции, используя формулу (а↔b)=(a—>b)/\(b—>a):

⌐(((z→x)—>(y│x)) /\ ((y│x)—>(z→x)))

Избавимся от импликации (a—>b=⌐a\/b)и от штриха Шеффера ( a|b=⌐ (a/\b) ):

( ( (⌐z\/x)—>( ⌐(y/\x) ) ) /\ (⌐ (y/\x) —> (⌐z\/x) ) )= =( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ (⌐(⌐(y/\x)) \/ (⌐z\/x) ) )

Используя свойство, что ⌐(⌐а)=а, получим

( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) )

Используя законы Де Моргана: ⌐ (a\/b)= ⌐a /\ ⌐b ; ⌐ (a/\b)= ⌐a \/ ⌐b , упростим

( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) ) = ⌐ ( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) \/ ((y/\x)
\/ (⌐z\/x))=

= (⌐ (z /\ ⌐x) /\ ( ⌐y \/ ⌐x) ) \/ (⌐ (y/\x) /\ (⌐z\/x))=((z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x)/\ (z/\⌐x))
Используя свойство дистрибутивности (a\/b)/\c=(a/\c) \/ (b/\c) , получим:

 (z /\ y /\ x) \/ (x /\y/\x) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\⌐x)

 Зная, свойство идемпотентности: а /\ а = а, получим ДНФ(дизъюнкция элементарных
конъюнкций)
исходной формулы:

(z /\ y /\ x) \/ (x /\y) \/ (⌐y/\z/\⌐x)\/(⌐x/\z)

Теперь получим СДНФ формулы, нужно чтобы в каждой конъюнкции
в ДНФ, были все слагаемые, для этого используем закон склеивания

a=(a /\ b) \/ (a /\ ⌐b)=a /\ (b \/ ⌐b):

(z /\ y /\ x) \/ (x /\y/\ (z \/ ⌐z)) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\ (y \/⌐y))

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

(z /\ y /\ x) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/
(⌐y/\z/\⌐x)\/(⌐x/\z/\ y) \/ (⌐x/\z/\⌐y)=

=( х /\ у /\ z) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x /\ y /\z) \/ (⌐x /\ ⌐y /\ z)
Уберем одинаковые слагаемые, получим СДНФ исходной формулы:

( х /\ у /\ z) \/ (x /\y/\ z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x/\ y /\z)

Приведем формулу ⌐((z→x)↔(y│x)) к КНФ (конъюнктивной нормальной
форме), то есть получим конъюнкцию дизъюнкций:
Выше мы избавились от эквиваленции, импликации, штриха
Шеффера и отрицания получили

⌐((z→x)↔(y│x))= ((z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x) /\ (z/\⌐x))

 Воспользуемся свойством дистрибутивности (a/\b) \/ c=(a\/c) /\ (b\/c):

((z \/ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\ ((y /\ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) )==(z \/ x \/ ⌐y\/⌐x) /\ (z \/ x \/ (z/\⌐x)) /\ ((y \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\(x\/((⌐y\/⌐x) /\ (z/\⌐x)))=
=(z\/ x \/ ⌐y\/⌐x)
/\ (z \/ x \/ z) /\ (z \/ x \/ ⌐x) /\ (y \/ ⌐y\/⌐x) /\ (y \/ (z/\⌐x)) /\ (х\/⌐y\/⌐x) /\ (x\/(z/\⌐x))=
=(z \/ x \/ ⌐y\/⌐x) /\ (z \/ x \/ z) /\ (z \/ x \/ ⌐x) /\ (y \/ ⌐y\/⌐x) /\ (y \/ z) /\ (y \/ ⌐x) /\ (х\/⌐y\/⌐x)
/\ (x\/z) /\ (x\/⌐x)=

Упростим множители за счет свойств a
\/ a =1, b\/1=1, a/\1=a

(z \/ ⌐y \/ 1) /\ (x \/ 1) /\ (z \/ 1) /\ (1\/⌐x) /\ (y \/ z) /\ (y \/ ⌐x) /\ (⌐y\/1) /\ (x\/z) /\ 1=

= 1 /\ 1 /\ 1 /\ 1 /\ (y \/ z) /\ (y \/ ⌐x) /\ 1 /\ (x\/z) /\ 1

Получили КНФ
(конъюнкция элементарных дизъюнкций)
исходной формулы:

(y \/ z) /\ (y \/ ⌐x) /\ (x\/z)

Теперь получим СКНФ исходной формулы, для этого в
дизъюнкциях из КНФ должны присутствовать все слагаемые, добавим с помощью
формул

(a /\ a =0, a\/0=a)не достающие слагаемые , получим (y \/ z\/(х /\ ⌐x)) /\ (y \/ ⌐x \/(z /\ ⌐z)) /\ (x\/z\/(y /\ ⌐y)), можно записать:
Используя свойство дистрибутивности, (y \/ z \/ х) /\( y \/ z\/ ⌐x) /\ (y \/ ⌐x \/ z ) /\ ( y
\/ ⌐x \/ ⌐z) /\ (x \/ z \/ y) /\ (x \/ z \/ ⌐y)

Избавимся от одинаковых множителей, получим СКНФ исходной формулы:
(x \/ y \/ z) /\ (⌐x \/ y \/ z) /\ (⌐x\/ y \/ ⌐z) /\ (x \/ ⌐y \/ z)

—>далее найдем полином Жегалкина

посмотреть еще задачи по дискретной математике