ИДЗ_Математическая_логика
.docxМІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ «ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»
Кафедра «Системний аналіз та управління»
Розрахункове завдання з дисципліни «Математична логіка»
(Варіант 1)
Виконав:
студент групи ІФ-83В
Бегашевський В.М.
Перевірив: Коваленко С.В.
Харків 2014
-
Запишите в словесном виде представленные логические высказывания, так чтобы они давали истинное и ложное значения:
((A˅B)→C)˄D.
Для того чтобы записать вышеприведенную формулу и она давала истинное значение обозначим: 2 + 2 = 4(A), 2 * 2 = 4(B), Киев — столица Украины(C), Вашингтон — столица США(D).
Распишем значения наших переменных:
A — истина.
B — истина.
C — истина.
D — истина.
Получим логическое высказывание: Если 2 + 2 = 4 или 2 * 2 = 4, то Киев — столица Украины; и Вашингтон — столица США.
Для того, чтобы записать вышеприведенную формулу и она давала ложное значение обозначим: 2 + 2 = 4(A), 2 * 2 = 4(B), Харьков — штат Америки(C), Тель-Авив — Израильский город(D).
Распишем значения наших переменных:
A — истина.
B — истина.
C — ложь.
D — истина.
Получим логическое высказывание: Если 2 + 2 = 4 или 2 * 2 = 4, то Харьков — штат Америки; и Тель-Авив — Израильский город.
-
Упростите формулы, приведя их к более простому виду. В качестве доказательства приведите таблицы истинности для исходной и получившейся формул:
¬(¬P˄¬Q)˅((P→Q)˄P)=(P˅Q)˅((¬P˅Q)˄P)=(P˅Q)˅((¬P˄P)˅(Q˄P))=(P˅Q)˅(P˄Q)=((P˅P˅Q)˄(P˅Q˅Q))=(P˅Q)˄(P˅Q)=P˅Q.
Таблица для исходной формулы F=¬(¬P˄¬Q)˅((P→Q)˄P):
|
P |
Q |
¬(¬P˄¬Q) |
P→Q |
((P→Q)˄P) |
F |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
Таблица для упрощенной формулы F1= P˅Q:
|
P |
Q |
F1 |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
-
Упростите данную систему истинных высказываний, найдя логически эквивалентную систему, состоящую из меньшего числа не более сложных высказываний:
C→(A˅B), (B˄C)→A, (A˄B)→C.
Исходя из условия, делаем вывод:
C→(A˅B)=1, (B˄C)→A=1, (A˄B)→C=1, тогда конъюнкция истинных высказываний дает нам формулу:
(C→(A˅B))˅((B˄C)→A)˅((A˄B)→C)=[(A˅B˅˅¬C)˄(A˅¬B˅¬C)]˄(¬A˅¬B˅C)=[(A˅¬C)˅(B˅¬B)]˄(¬A˅B˅C)=(A˅¬C)˄(¬A˅¬B˅C).
Из результирующей формулы извлекаем систему истинных высказываний: (A˅¬C), (¬A˅¬B˅C).
-
Упростите данную систему высказываний, найдя логически эквивалентную ей систему, если известно, что в данной системе, как минимум, одно высказывание истинно:
¬(A→B), ¬B˄A, ¬D˄C, ¬(C→A).
Исходя из условия, делаем вывод, что дизъюнкция высказываний, из которых может быть истинно хотя бы одно и более высказывания, даст нам формулу:
(¬(A→B))˅(¬B˄A)˅(¬D˄C)˅(¬(C→A))=(¬(¬A˅B))˅(¬B˄A)˅(¬D˄C)˅(¬(¬C˅˅A))=(A˄¬B)˅(A˄¬B)˅(C˄¬D)˅(¬A˄C)=(A˄¬B)˅(C˄¬D)˅(¬A˄C).
Из результирующей формулы извлекаем систему высказываний:
(A˄¬B), (C˄¬D), (¬A˄C).
-
Для представленной формулы алгебры высказываний найти ее СДНФ и СКНФ. Расчеты выполнить как с помощью построения таблицы истинности формулы, так и с помощью равносильных преобразований:
¬(X˄Y)→¬(X˅Z).
Приводим данную формулу к ДНФ:
FДНФ=¬(X˄Y)→¬(X˅Z)=(X˄Y)˅¬(X˅Z)=(X˄Y)˅(¬X˄¬Z).
Приводим ДНФ к СДНФ:
FСДНФ=(X˄Y)˅(¬X˄¬Z)=((X˄Y)˄(Z˅¬Z))˅((¬X˄¬Z)˄(Y˅¬Y))=(X˄Y˄Z)˅(X˄Y˄˄¬Z)˅(¬X˄Y˄¬Z)˅(¬X˄¬Y˄¬Z).
Приводим СДНФ к СКНФ:
¬F=(¬X˄¬Y˄Z)˅(¬X˄Y˄Z)˅(X˄¬Y˄¬Z)˅(X˄¬Y˄Z).
FСКНФ=(X˅Y˅¬Z)˄(X˅¬Y˅¬Z)˄(¬X˅Y˅Z)˄(¬X˅Y˅¬Z).
Построим таблицу истинности для исходной формулы F=¬(X˄Y)→¬(X˅Z):
|
X |
Y |
Z |
¬(X˄Y) |
¬(X˅Z) |
F |
|
0 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
1 |
Составим СДНФ формулы F по таблице истинности, выбрав строки, в которых формула дает истинное значение, и запишем по правилу: если переменная в этой строке ложная — мы записываем её с отрицанием в конъюнктивный одночлен, если она истинная — записываем без отрицания. Между одночленами расставляем знаки дизъюнкции:
FСДНФ=(X˄Y˄Z)˅(X˄Y˄¬Z)˅(¬X˄Y˄¬Z)˅(¬X˄¬Y˄¬Z).
Составим СКНФ формулы F по таблице истинности, выбрав строки, в которых формула дает ложное значение, и запишем по правилу: если переменная в этой строке ложная — мы записываем её без отрицания в дизъюнктивный одночлен, если она истинная — записываем с отрицанием. Между одночленами расставляем знаки конъюнкции:
FСКНФ=(X˅Y˅¬Z)˄(X˅¬Y˅¬Z)˄(¬X˅Y˅Z)˄(¬X˅Y˅¬Z).