Контрольная работа: Логика высказываний

Муниципальное образовательное учреждение высшего профессионального образования

Южно-Уральский профессиональный институт

Факультет управления и информационных технологий

Кафедра информатики и вычислительной техники

Контрольная работа

по дисциплине «Математическая логия и теория алгоритмов»

Студент

гр. ВМз-01-08, факультет УиИТ

____________________ М.О.Белозерова

«__»___________2009

Преподаватель

___________________ С.А. Рудаков

к.п.н. «__»___________2009

Челябинск

2009

1. Задание по логике высказываний

Ниже приведены по три клаузы в одном варианте. Каждую клаузу необходимо доказать следующими методами: резолюций и с помощью таблиц истинности.

a. А, В v С => А & В; С

b. B vС, (А -> В) -> (С -> А) => А

c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (Av В),

D -> (А -> В), С -> (В vD), Av С vD, С -> (А -> В) => А & В & С; А & В & D

Докажем с помощью метода резолюций истинность следующей клаузы:

a. А, В v С => А & В; С

Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

A, В v C, -B v -C, -A => 0

P1 P2 P3 P4

Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:

Докажем с помощью метода резолюций истинность следующей клаузы:

Bv С, (А -> В) -> (С -> А) => А

Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

В v С, A v -B v -C, -A => 0

P1 P2 P3

Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:

Докажем с помощью метода резолюций истинность следующей клаузы:

c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (Av В),

D -> (А -> В), С -> (В vD), Av С vD, С -> (А -> В) => А & В & С;

А & В & D

Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

А v В v С, -В v -Dv А, -С v –В v А, -А v -В v С, -DvAv В, P1 P2 P3 P4 P5 Dv -А v В,

- С v В vD, Av С vD,

-С v -А v В, -А, -В, -С v -А, -В, -D =>0 P6 P7 P8 P9 P10 P11 P12 P13 P14

Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:

Докажем с помощью таблиц истинности следующую клаузу:

А, В v С => А, В vС

P1 P2 C1 C2

Докажем с помощью таблиц истинности следующую клаузу:

Bv С, (А -> В) -> (С -> А) => А

P1 P2 C1

Теперь составим таблицу истинности (табл. 1.1) , в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р.

Клауза считается ложной , т.к. единицы следствия (С1) не накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины не образуют подмножество единиц следствия.

Докажем с помощью таблиц истинности следующую клаузу:

А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (Av В),

P1 P2 P3 P4 P5

D -> (А -> В), С -> (В vD), Av С vD, С -> (А -> В) => А & В & С; А & В & D

Р6 Р7 Р8 Р9 С1 C2 C3 C4 C5

Теперь составим таблицу истинности (табл. 1.3) , в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р.

Клауза считается истинной , т.к единицы следствия (С1) накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины образуют подмножество единиц следствия.

2. Составление легенды по клаузе

Клауза 1: А, В v С => А & В; С

Машина едет по Копейскому шоссе. На дороге опасно, так как она покрыта льдом или мокрая. Итак, машина едет по шоссе или по ледяной дороге или по мокрой.

Клауза 2: Bv С, (А -> В) -> (С -> А) => А

Студент Иванов находился на уроке или в коридоре. На уроке была контрольная работа, Иванов получил четвертку, то он был на уроке, он был в коридоре, не смотря на то, что он получил четверку. Это говорит о том, что у студента Иванова есть, стремление хорошо учится.

3. Составление клаузы по легенде

Ниже приведена легенда. Запишите с использованием 4—6 различных букв клаузу, отвечающую тексту или контексту вашей легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное, другое ложное. С помощью таблицы истинности найдите МНФ, минимальное и все трансверсальные покрытия.

Увеличение денег в обращении влечет за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, тогда избежим безработицы и курс денежной единицы останется неизменным.

Можно составить следующую клаузу:

A → B, A→ (CvD), D→ (E&F), B→ G => (C & -F) → (-E & G)

Введем обозначения:

A– Увеличение денег (денежная масса, курс денежной единицы);

B– Инфляция;

C – Денежная эмиссия;

D – Снижение товарооборота;

E– Безработица;

F – Спад производства;

G – курс денежной единицы.

Увеличение денег в обращении влечет за собой инфляцию (A → B). Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота (A → (CvD)). Снижение товарооборота приводит к безработице и спаду производства (D → (E&-F)).

Из-за инфляции падает курс денежной единицы (B → G). Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство(C & F), тогда избежим безработицы и курс денежной единицы останется неизменным (-E & G).

Из таблицы видно, что четыре единицы обобщенной посылки (Р) не покрываются единицами ложного следствия (-Е); единицы же истинного следствия (Е -> (В & D )) целиком накрывают единицы обобщенной посылки.

4. Задание по логике предикатов

Установить истинность логического выражения своего варианта путем конкретизации.

х y (А(x) -> В(у)) = х A(x) -> x В(х)

Доказательство: