Описание всех лабораторных работ (1006390), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Приведем пример. Докажем, что формула G=YX не является логическим следствием формул F₁=XY, F₂=XY, F₃=Y. Для этого построим совместную таблицу истинности формул F₁,F₂,F₃ и G.

Таблица 1.4

X	Y	F1=XY	F2=XY	F3=X	G=YX
1	1	1	1	1	1
1	0	1	0	0	1
0	1	1	1	1	0
0	0	0	1	0	1

Мы видим (см. таблицу 1.4), что если взять интерпретацию , для которой (х)=0, (y)=1, (т.е. взять третью строку таблицы), то (F₁)=(F₂)=(F₃)=1, но (G)=0. Следовательно, формула G не является логическим следствием формул F₁,F₂,F₃.

Понятие логического следствия тесно связано с понятием выполнимости.

Определение. Множество формул {F₁,F₂,…,F_l} называется выполнимым, если существует интерпретация  такая, что (F₁)=(F₂)=…=(F_l)=1.

Проверку выполнимости множества формул {F₁,F₂,…,F_l} можно провести построением совместной таблицы истинности этих формул. Если найдется хотя одна строка, в которой в столбцах формул F₁,F₂,…,F_l стоят единицы, то это множество формул выполнимо. Если такой строки нет, то множество формул невыполнимо. Так, множество формул {F₁,F₂,F₃,G} из предыдущего примера выполнимо, поскольку в таблице 1.4 в первой строке в столбцах этих формул стоят единицы.

Теорема 1.2 Формула G является логическим следствием формул F₁,F₂,…,F_k тогда и только тогда, когда множество формул

L={F₁,F₂,…,F_k,G}

невыполнимо.

Задачи для самостоятельной работы

1. Будут ли следующие формулы тождественно истинны:

а) X & Y  X,	б) X  Y  Х,	в) X & Y  Х  Y ,
г) X  Y  X & Y,	д) (ХY)(YХ),	е) (ХX)X,
ж) (XX)X ,	з) (XY)(YX),	и) (XY)(XY)?

2. Существует ли формула F такая, что формула G тождественно истинна:

а) G = X & Y   (F & Z);	б) G = (F & YZ) (ZY);
в) (F&Z) ∨ (¬F&¬Y&¬Z)

3. Будут ли следующие формулы равносильны:

а) Х  Y и Y X,	б) X Y и Y  Х
в) Х (YZ) и (ХY) Z,	г) Х  (Y  Z) и X & Y Z,
д) (X  Y ) и X Y,	е) XY и XY?

4. Доказать равносильность формул:

а) [(XY)&(X&Z)] и XZ,	б) (X&Y)(X&Y) и (X&Y)
в) [(XY)&Y]&(X&Y) и Y	г)  [(X & Y)  Z] и  (ZX)  (ZY),
д) (X & Y)  (X & Y)  (X & Y) и Х  Y,
е) (X & Y & Z)  (X & Y & Z)  (Y & Z) и (XY)&Z.

5. Доказать, что формула G является логическим следствием формул F₁,F₂,...,F_n:

а) F1=X  Y  Z, F2=ZW, F3=W, G=XY;

б) F1=XYZ, F2=XX1, F3=YY1, F4=Z, G=X1Y1;

в) F1=XY&Z, F2=YZ1Z2, F3=ZZ1, F4=Z1, G=XZ2;

г) F1=ZZ1, F2=Z1Y, F3=XYZ, G=XY.

6. Доказать, что формула G не является логическим следствием формул F₁,F₂,…,F_n:

а) F1=XYZ, F2=YW, F3=ZX, G=X  W;

б) F1=XY, F2=YZ, F3=ZZ1Z2, G=XZ1;

в) F1=XYZ, F2=XX1, F3=YХ1Y1, F4=Y1, G=ZX1.

7. Определить, какая логическая связка используется в следующих выражениях: "А, если В", "коль скоро А, то В", "в случае А имеет место В", "как А, так и В", "для А необходимо В", "для А достаточно В", "А вместе с В", "А не имеет места", «A, только если B», «или A, или B», «A одновременно с B», «A – то же самое, что и B».

Варианты задач по бригадам

Записать следующие рассуждения в виде последовательности формул логики высказываний. Будет ли логичным рассуждение?

1. Профсоюзы штата будут поддерживать губернатора, если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.

2. Если мы не будем продолжать политику сохранения цен, то мы потеряем голоса фермеров. Если же мы будем продолжать эту политику и не прибегнем к контролю над производством, то продолжится перепроизводство. Без голосов фермеров нас не переизберут. Значит, если нас переизберут, и мы не прибегнем к контролю над производством, то продолжится перепроизводство.

3. Если завтра будет хорошая погода, то я буду кататься на коньках или я пойду на лыжах. Если я пойду на лыжах, то лучше поехать за город, а если буду кататься на коньках, то останусь в городе. Мне не хочется завтра в выходной день оставаться в городе. Следовательно, если завтра будет хорошая погода, то я пойду на лыжах.

4. Если Джонс не встречал этой ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Эксперты установили, что убийство произошло до полуночи. Следовательно, Смит был убийцей.

5. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.

6. Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

7. Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен и волнения не прекратятся до тех пор, пока участникам волнений это не надоест, и власти не начнут примирительные действия. Следовательно, если губернатор не желает взять на себя ответственность и участникам волнений это не надоест, то волнения не прекратятся.

Инструкция по установке и выполнению программы

На компьютере должен стоять интерпретатор Ruby. Его можно скачать с сайта ruby-lang.org.

Программа запускается из командной строки. Пример запуска программы:

ruby tautology.rb "(x -> y) <=> ((not y)->(not x))"

У программы есть единственный параметр, заключенный в двойные кавычки – это требуемая функция.

При задании функции используются следующие обозначения:

and - конньюнкция

or - дизьюнкция

not - отрицание

-> - импликация

<=> - эквиваленция.

В неатомарных формулах необходимо в обязательном порядке использовать скобки!

Программа сообщает, что функция является тавтологией или первое найденное ложное значение функции.

Для сохранения результатов в файл следует перенаправить стандартный вывод командой >>. Например:

ruby tautology.rb "(x -> y) <=> ((not y)->(not x))" >> res.txt

Лабораторная работа № 2. Логика предикатов

Цель работы – научиться переводить выражения на естественном языке на язык логики предикатов. Научиться приводить предикат к нормальным формам. Научиться использовать логику предикатов для формализации информационных систем.

Порядок выполнения

1. Ознакомиться с методическими указаниями.

2. Решить цикл задач для самостоятельной работы.

3. Провести формализацию задачи (вариант задачи определяется номером бригады).

4. Составить необходимые запросы к информационной системе в логике предикатов. Привести формулы к ПНФ.

5. Поверить правильность запросов на ЭВМ (использовать программу predicate.rb).

6. Оформить отчет.

Методические указания

Логика высказываний обладает довольно слабыми выразительными возможностями. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

Определение. Пусть М – непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М.

Рассмотрим примеры. Пусть М есть множество натуральных чисел N. Тогда выражения «x – простое число», «x – четное число», «x – больше 10» являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д. Выражения «x больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x плюс y равно z», «|x-y|z».

Будем считать, что высказывание – нульместный предикат, то есть предикат, в котором нет переменных.

Надо отметить, что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение «существует число x такое, что y=2x» на множестве натуральных чисел определяет одноместный предикат. По смыслу этого выражение в нем можно заменять только переменную y. Например, замена y на 6 дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».

Предикат с заменяемыми переменными x₁,…,x_n будет обычно обозначаться заглавной латинской буквой. После которой в скобках указаны эти переменные. Например, P(x₁,x₂), Q(x₂,x₃), R(x₁). Среди переменных в скобках могут быть и фиктивные.

На совокупности всех предикатов, заданных на множестве М, вводятся знакомые операции конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция.

Характеристики

Список файлов лабораторной работы