Логика высказываний

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

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

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

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

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

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

Студент

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

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

«__"___________2009

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

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

к.п.н. «__"___________2009

Челябинск

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

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

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

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

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

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D

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

a. А, В v С => А & В; С Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

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

P1 P2 P3 P4

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

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

B v С, (А -> В) -> (С -> А) => А Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

В v С, A vB vC, -A => 0

P1 P2 P3

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

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

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

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С;

А & В & D

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

А v В v С, -В vD v А, -С vВ v А, -А vВ v С, -D v A v В, P1 P2 P3 P4 P5 D vА v В,

— С v В v D, A v С v D,

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

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

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

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

P1 P2 C1 C2

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

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

P1 P2 C1

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

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

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

А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D — > (A v В),

P1 P2 P3 P4 P5

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D

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

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

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

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

Клауза 1: А, В v С => А & В; С Машина едет по Копейскому шоссе. На дороге опасно, так как она покрыта льдом или мокрая. Итак, машина едет по шоссе или по ледяной дороге или по мокрой.

Клауза 2: B v С, (А -> В) -> (С -> А) => А Студент Иванов находился на уроке или в коридоре. На уроке была контрольная работа, Иванов получил четвертку, то он был на уроке, он был в коридоре, не смотря на то, что он получил четверку. Это говорит о том, что у студента Иванова есть, стремление хорошо учится.

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

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

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

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

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

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

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

B — Инфляция;

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

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

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

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

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

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

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

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

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

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

х y (А (x) -> В (у)) = х A (x) -> x В (х) Доказательство: