Для примеров из п. 6 построить доказательство, используя метод обратной дедукции

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

1) если пойти на первую пару, то надо встать рано, а если играть в преферанс, то лечь придется поздно;

2) если лечь поздно и рано встать, то спать придется мало;

3) мало спать нельзя.

Заключение: надо или не играть в преферанс, или не идти на первую пару.

Введем следующие обозначения для высказываний:

g – встать рано;

d – играть в преферанс;

с – идти на первую пару;

s – лечь поздно спать;

e – мало спать.

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

Теперь построим доказательство, используя метод резолюций. Для этого приведем имеющиеся гипотезы к форме дизъюнктов:

.

Отрицание следствия будет иметь вид .

1. 2. 3. 4. 5. c 6. d 7. g (1-5) 8. s (2-6) 9. (3-7) 10. e (8-9) 11. Пустой дизъюнкт (4-10) 1.

9. Записать формально следующее рассуждение на естественном языке в терминах логики высказываний и доказать его справедливость, используя метод резолюций:

а) Посылки: Если идет дождь, то нежарко. Если светит солнце, то жарко. Идет дождь.

Заключение: Нежарко и не светит солнце.

б) Посылки: Экзамен сдан вовремя или сессия продлена. Если сессия продлена, то не сдана курсовая работа или не зачтены лабораторные работы. Курсовая работа сдана. Экзамен вовремя не сдан.

Заключение: Неверно, что если курсовая работа сдана, то лабораторные работы зачтены.

в) Посылки: Если имеет место денежная эмиссия, то растет курс доллара. Если эмиссии нет и инфляция не растет, то курс доллара не растет. Инфляция не растет.

Заключение: Имеет место эмиссия и растет курс доллара или нет эмиссии и курс доллара не растет.

г) Посылки: Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет.

Заключение: Стоимость жизни увеличится.

д) Посылки: Если 2 - простое число, то это наименьшее простое число. Если 2 - наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число.

Заключение: 2 - простое число.

е) Посылки: Джон или переутомился, или он болен. Если он переутомился, то он раздражается. Он не раздражается.

Заключение: Джон болен.

ж) Посылки: Если завтра будет холодно, то я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен.

Заключение: Я не надену теплое пальто.

з) Посылки: Если исход скачек будет предрешен сговором или в игорных домах будут орудовать шулеры, то доходы от туризма упадут и город пострадает. Если доходы от туризма упадут, полиция будет довольна. Полиция никогда не бывает довольна.

Заключение: Исход скачек не предрешен сговором.

и) Или Вася и Петя одного возраста, или Вася старше Пети. Если Вася и Петя одного возраста, то Федя и Петя не одного возраста. Если Вася старше Пети, то Петя старше Семена.

Заключение: Или Федя и Петя не одного возраста, или Петя старше Семена.

к) Посылки: Если будет идти снег, то машину будет трудно вести. Если будет трудно вести машину, то я опоздаю, если не выеду пораньше. Идет снег.

Заключение: Я должен выехать пораньше.

л) Посылки: Если подозреваемый совершил кражу, то она либо была тщательно подготовлена, либо он имел соучастника. Если бы кража была подготовлена тщательно, то, если бы был соучастник, то украдено было бы гораздо больше. Украдено мало.

Заключение: Подозреваемый невиновен.

м) Посылки: В бюджете возникнет дефицит, если не повысить налоги. Если в бюджете имеется дефицит, то государственные расходы на социальные нужды сокращаются.

Заключение: Если повысить налоги, то государственные расходы на социальные нужды не сокращаются.

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

Заключение: Атака не удастся.

7.3. ЛОГИКА ПРЕДИКАТОВ

1. Пусть заданы предикаты: - x - четное число и - x - число, кратное трем. Предикаты определены на множестве N - натуральных чисел. Определить области истинности предикатных выражений:

а)

б)

в)

г) .

2. Пусть Р(х) обозначает «х - простое число», Е(х) -«х - четное число», О(х) - «х - нечетное число» и D(x,y) - «у делится на х». Перевести на русский язык следующие предикатные выражения:

1) Р (7);

2) Е (2) &Р (2);

3)

4)

5)

6)

7)

8)

Пусть предикаты определены на множестве N - натуральных чисел:

- - n делится на 3;

- - n делится на 2;

- - n делится на 4;

- - n делится на 6;

- - n делится на 12.

Определить, какие из предикатных выражений истинные, а какие – ложные:

а) ;

б) ;

в) ;

г) .

4. Найти отрицание следующих формул:

а) ;

б) .

Пример. Доказать тождественную истинность заданного предикатного выражения

Пример. Доказать тождественную ложность заданного предикатного выражения

Определить, какие из приведенных формул являются тождественно истинными, а какие - тождественно ложными:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

4. Привести к нормальной форме следующие выражения:

а) ;

б) ;

в) .

5. Представить утверждения, сформулированные на естественном языке в виде предикатных выражений:

1) все судьи — юристы (J(x) обозначает «х - судья»; L(x) обозначает «х - юрист);

2) некоторые юристы — жулики (S(x) обозначает «х - жулик»);

3) ни один судья не является жуликом;

4) некоторые судьи — старики, но бодрые (O(x) обозначает «х - старый»; V(x) обозначает «х - бодрый»);

5) судья Сидоров не стар и не бодр (константу «Сидоров» обозначает символ «j»);

6) не все юристы — судьи;

7) некоторые юристы, являющиеся политиками, - члены государственной Думы (P(x) обозначает «х - политик»; C(x) обозначает «х - член государственной Думы»);

8) ни один член государственной думы не бодр;

9) все старые члены государственной думы - юристы;

10) некоторые женщины одновременно являются юристами и членами государственной думы (W(x) обозначает «х - женщина»);

11) ни одна женщина не является одновременно политиком и домашней хозяйкой (Н(х) обозначает «х - домашняя хозяйка»);

12) некоторые женщины-юристы являются домашними хозяйками;

13) все женщины-юристы восхищаются каким-нибудь судьей (А(х,у) обозначает «х - восхищается y);

14) некоторые юристы восхищаются только судьями;

15) некоторые юристы восхищаются женщинами;

16) некоторые жулики не восхищаются ни одним юристом;

17) судья Сидоров не восхищается ни одним жуликом;

18) существуют как юристы, так и жулики, которые восхищаются судьей Сидоровым;

19) только судьи восхищаются судьями;

20) все судьи восхищаются только судьями.

Пример. Доказать с помощью метода резолюций справедливость следующих рассуждений.

1. Некоторые руководители с уважением относятся ко всем программистам.

2. Ни один руководитель не уважает бездельников.

Следовательно, ни один программист не является бездельником.

Введем следующие предикаты:

C(x) – «x – руководитель»;

P(x) – «x – программист»;

B(x) – «x – бездельник»;

U(x,y) – «x уважает y».

Тогда посылки, записанные в виде предикатных выражений, будут выглядеть так:

1) ;

2) .

Заключение примет следующий вид:

.

Преобразовав посылки и следствие, которое надо взять с отрицанием, в совокупность дизъюнктов, получим множество предложений, невыполнимость которого докажем, используя метод резолюций. Имеем

:

1)
2)
3)
4)
5)
6)		(1 - 3)	S={a/x}
7)		(2 - 4)	S={b/y}
8)		(6 - 7)	S={a/x, b/y}
9)	Пустой дизъюнкт	(5 - 8)

6. Представить утверждения, сформулированные на естественном языке в виде множества предикатных выражений. Доказать их справедливость, используя метод резолюций:

1) Все мексиканцы носят сомбреро. Ни одна обезьяна не носит сомбреро. Следовательно, ни одна обезьяна не является мексиканцем.

2) Каждый член демократической партии голосует за президента и не любит коммунистов. Некоторые демократы являются предпринимателями. Следовательно, существуют предприниматели, которые не любят коммунистов.

3) Все отцы – мужчины. Если у детей один отец, то они единокровны. Брат – это единокровный мужчина. Джон – отец Боба. Джон – отец Сида. Сид – отец Лиз. Следовательно, Сид и Боб - братья.

4) Ни один человек не является четвероногим. Все женщины – люди. Следовательно, ни одна женщина не является четвероногой.

5) Некоторые республиканцы любят всех демократов. Ни один республиканец не любит ни одного социалиста. Следовательно, ни один демократ не является социалистом.

6) Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекаются к ответственности. Следовательно, не все привлекающиеся к ответственности являются торговцами наркотиками.

7) Все рациональные числа являются действительными числами. Некоторые рациональные числа – целые числа. Следовательно, некоторые действительные числа – целые числа.

8) Все первокурсники общаются со всеми второкурсниками. Ни один первокурсник не общается ни с одним студентом последнего курса. Следовательно, ни один второкурсник не является студентом последнего курса.

9) Некоторым нравится группа «Queen». Некоторые не любят никого, кому нравится группа «Queen». Следовательно, некоторых любят не все.

10) Каждый родитель имеет ребёнка. Если родитель – женщина, то это – мать. Лиз – женщина. Анна – родитель Лиз. Следовательно, Анна – мать.

11) Если родитель – мужчина, то это отец. Если ребёнок – мужчина, то это сын. Иван – мужчина. Сидор – мужчина. Иван – отец Сидора. Следовательно, Иван – отец и Сидор – сын.

12) Если два человека являются родственниками третьего, то первый – родственник второго. Каждый – чей-нибудь родственник. Значит, если Иван – родственник Петра, а Петр – родственник Сидора, то Иван – родственник Сидора.

13) Таможенники возвращают всех, кто въехал в страну без паспорта. Люди на машинах въехали в страну и были возвращены только другими людьми на машинах. Ни один человек на машине не имел паспорта. Следовательно, некоторые таможенники были на машинах.

7. Используя метод резолюций для предикатных выражений для заданного множества гипотез Н={h₁, h₂ ,..., h_n} и утверждения S, доказать справедливость выражения Н |- S:

1)	h1 = "x(K(x)&"y(R(y)®U(x, y))), h2 = "x(K(x)®"y(B(y)® (x, y))), S = "y(R(y)® (y));
2)	h1 = "x(T(x)® (x)), h2 = $x(N(x)&O(x)), S = $x(N(x)& (x));
3)	h1 = "x(C(x)®W(x)&R(x)), h2 = $x(C(x)&O(x)), S = $x(P(x)&R(x));
4)	;
5)	h1 = "x(P(x)®Q(x)), h2 = "x(Q(x)®R(x)), S = "x(P(x)®R(x));
6)	h1 = "x"y(F(x, y)®M(x)), h2 = "x"y"w(F(x, y)&F(x, w)®E(y, w)), h3 = "x"y(E(x, y)&M(x)®B(x, y)), h4 = F(Y, H), h5 = F(Y, D), h6 = F(D, L), S = B(z, H);
7)	h1 = "z(H(z)® (z)), h2 = "y(W(y)®H(z)), S = "x(W(x)® (x));
8)	h1 = "x"y(P(x)&V(y)®W(x, y)), h2 = "x"y(P(x)&E(y)® (x, y)), S = "x(V(x)® (x));
9)	h1 = "x"y(R(x, y)&M(x)®O(x)), h2 = "x"y(R(x, y)&M(y)®C(y)), h3 = M(D), h4 = M(B), h5 = R(D,B), S = O(D)&C(B));
10)	h1 = "x(M(x)®W(x)), h2 = "x(N(x)® (x)), S = "x(N(x)® (x));
11)	h1 = "x(D(x)® (x,K)), h2 = $x(D(x)&P(x)), S = $x(P(x)& (x,K));
12)	h1 = $x (H(x)&U(x,Q)), h2 = $x"y(H(x)&H(y)& U(x,Q)® (x,y)), S = $x$y(H(x)&H(y)&L(x,y));
13)	h1 = "z(H(z)&R(z)® (z)), h2 = "y(W(y)®H(z)), h3 = R(A), h4 = W(x), S = "x( (x)& (x)).

7.4. ТЕОРИЯ АЛГОРИТМОВ

Пример. Пусть на ленте записаны два натуральных числа в унарном коде (унарный код - это представление числа в виде соответствующей последовательности единиц. Например, 4=1111=1⁴). Числа разделены символом «+». Требуется реализовать операцию сложения таким образом, чтобы после ее реализации на ленте были сохранены исходные данные и записан результат выполнения операции. Управляющее устройство после завершения работы должно находиться на первом символе текущей записи на ленте.

Начальное состояние МТ, например, для чисел 2 и 4 должно иметь вид:

А заключительное:

В основе алгоритма будет лежать следующая идея, записав символ «=», после исходных данных, за ним следует скопировать все единицы из первого и второго числа, после чего вернуть управляющее устройство в первую позицию записи на ленте. Опишем МТ в виде системы команд:

Множества A и Q определены так:

8. Построить машину Тьюринга, реализующую заданную функцию. Описание машины должно быть представлено в виде системы команд, графа переходов или таблицы. Считать, что исходные данные записаны на ленте, на ней же они должны быть сохранены после выполнения всех действий. Результаты записываются на ленте после исходных данных и отделяются от них символом «=»:

а) Пусть на ленте записана последовательность нулей и единиц. Реализовать машину, которая будет подсчитывать число единиц в исходной последовательности и записывать результат счета;

б) Реализовать функцию, которая в выражении в бинарной форме записи будет подсчитывать количество комбинаций вида 010. Например, 1101101010101=11;

в) Реализовать функцию, которая в выражении в бинарной форме записи будет подсчитывать количество комбинаций вида 101. Например, 01101110001011010=111;

г) Реализовать функцию, которая в выражении в бинарной форме записи будет производить замену комбинации 01 на 1, а 10 на 0. Считать, что такие комбинации в исходном выражении являются взаимно непересекающимися или отделены друг от друга символами. Например, 01111001110001=111011001;

д) ;

е) ;

ж)

з)

и)

к) Реализовать функцию, которая в выражении в унитарной форме записи будет каждую третью единицу заменять на ноль. Например, 1111111 = 1101101;

л) . Символ «[ ]» означает выделение целой части от результата деления. Считать, что x > y;

м) ;

н) ;

о) . Считать, что x > y;

п) .

7.5. ЭЛЕМЕНТЫ ТЕОРИИ НЕЧЕТКИХ МНОЖЕСТВ

1. Пусть задано множество студентов С ={Иванов, Петров, Сидоров, Федоров}. Определить на нем следующие нечеткие множества: S – трудолюбивых студентов, P – ленивых студентов и U – студентов, успешно сдавших сессию. Найти результаты следующих операций над множествами:

2. Пусть задано два множества E={a,d,f,r} и Y={10,20,15,55}, на которых определены нечеткие множества E и T, соответственно определить отношение между E и T, если эти множества заданы следующим образом:

E = , T = .

3. Пусть задано множество студентов С = {Иванов, Петров, Сидоров} и множество курсовых проектов K={k₁,k₂,k₃,k₄}. Определить на множестве студентов нечеткое множество S – сильных студентов, а на K – множество P – сложных курсовых проектов. Определить нечеткое отношение, которое будет соответствовать утверждению: «Если студент сильный, то он будет защищать сложный курсовой проект».

4. Пусть задано множество курсовых проектов K={k₁,k₂,k₃,k₄}, на котором определено нечеткое множество P – непростых курсовых проектов и задано множество D={d₁,d₂,d₃,d₄,d₅} – дипломных проектов, на котором определено нечеткое множество H - хороших дипломных проектов. Определить нечеткое отношение, которое будет соответствовать утверждению: «Если курсовой проект непростой, то из него можно сделать хороший дипломный проект».

5. Пусть заданы два нечетких отношения U и B:

;

.

Определить их свертку .

6. Используя результаты примеров 3 и 4 построить свертку нечетких отношений, которая будет соответствовать утверждению: «Если студент сильный, то у него получится хороший дипломный проект».