Краткая методичка по логике (стр. 5 из 10)

p – он является членом финансового комитета

q – он является членом дирекции

r – он является членом библиотечного фонда

(pÞq)Ù(ØpÞØ(qÙr))Ù(rÞØp) = (`p + q)(p +`q +`r)(`r +`p) = (`p +q)

= (`p + q) =(`p + q)(`p`q +`r) = (`p + q)(`p + q)`q +`r) = (`p + q)(`q +`r) = (pÞq)ÙØ(qÙr)

Таким образом, можно отбросить подчеркнутую часть текста.

Пример анализа рассуждения «(это преступление совершено в Кустанае |q). (Петров во время совершения преступления находился в Ростове |r). Следовательно (Петров не совершал этого преступления |Øp)».

qÙrÞØp – не тавтология

«Преступление совершено в Кустанае. Поэтому если Петров совершил это преступление, то (он во время совершения преступления находился в Кустанае |s). Но Петрова в это время в Кустанае не было. Значит, Петров не совершал этого преступления».

qÙ(qÞpÞs)ÙØp = … = 1 – тавтология т.е. рассуждение правильное.

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

(pÞs)ÙØsÞØp =

+`p = +`p = p + s +`p = 1 + s = 1

Задача. Выяснить, кто из четверых виновен на основе информации «Петров виновен, только если виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет».

p, q, r, s – виновен Петров, Кулагин, Родионов, Сидоров.

(pÞq)ÙØ(rÞs)ÙØ(qÙØs) = (`p + q)

= (`p + q) r`s(`q + s) = (`p + q)`r s`q = `p`q r`s

т.е. Родионов виновен, остальные не виновны.

Задача Кислера. Обвиняемые в подделке налоговых документов Браун, Джонс и Смит дают под присягой такие показания.

Браун: Джонс виновен, а Смит не виновен.

Джонс: Если Браун виновен, то виновен и Смит.

Смит: Я не виновен, но хотя бы один из них двоих виновен.

Вопрос 1: Совместимы ли данные показания?

Вопрос 2: Какое показание следует из другого?

Вопрос 3: Если все виновны, то кто лжесвидетельствует?

Вопрос 4: Если все сказали правду, то кто виновен?

Вопрос 5: Если невинный говорит правду, а виновный лжет, то кто виновен, а кто невиновен?

Б – виновен Браун.

Д – виновен Джонс.

С – виновен Смит.

Б	Д	С	ØБ	ØД	ØС	БÚД	ДÙØС	БÞС	ØСÙ(БÚД)
Л	Л	Л	И	И	И	Л	Л	И	Л
Л	Л	И	И	И	Л	Л	Л	И	Л
Л	И	Л	И	Л	И	И	И	И	И
Л	И	И	И	Л	Л	И	Л	И	Л
И	Л	Л	Л	И	И	И	Л	Л	И
И	Л	И	Л	И	Л	И	Л	И	Л
И	И	Л	Л	Л	И	И	И	Л	И
И	И	И	Л	Л	Л	И	Л	И	Л
Показания							Брауна	Джонса	Смита

1. Да, только за счет третьей строки.

2. Из первого третье.

3. Браун и Смит.

4. Джонс виновен, остальные невиновны.

5. Джонс невиновен, остальные виновны.

Тема 4. Кванторная логика.

или логика предикатов является расширением пропозициональной логики путем изучения операций ", $. Из определения этих операций следует, что значения высказываний "хp, $хp, понимаются соответственно как конъюнкция p₁Ùp₂Ùp₃Ù… и дизъюнкция p₁Úp₂Úp₃Ú… значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации.

Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание "хpÞ$хp является кванторологически истинным, но не является тавтологически истинным.

Истинностная таблица.

"хp	$хp	"хpÞ$хp
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

Истинностная схема.

p1, p2, p3…	"хp p1Ùp2Ùp3Ù…	$хp p1Úp2Úp3Ú…	"хpÞ$хp
ЛЛЛ…	Л	Л	И
ЛЛЛ…	Л	И	И
………	…	…	…
ИИИ…	И	И	И

Высказывание q называется кванторологическим следствием (из) высказываний р₁,…,p_n, если p является истинным в любой интерпретации, в которой истинными являются p₁,…,p_n.

Вхождением переменной c в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида "х(q) или вида $х(q); в противном случае это вхождение называется свободным.

Например, первое и второе вхождения c₁ в высказывание

((g

(c₁))Ù(g (c₁, c₂)))Þ($c₁(g (c₁)))

являются свободными, а третье и четвертое – связанными.

Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f

(c₅) является допустимым заменителем для c₆ в высказывании g ((c₅, (c₆), и не является

допустимым заменителем для c₆ в высказывании $c₅ (g

(c₅, c₆)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных.

Теорема о всезначности переменной: р = И тттк "хр = И

Теорема об отрицании обобщения и подтверждения:

Ø"хр равносильно $хØр

Ø$хр равносильно "хØр

Теорема о взаимоисключении кванторов:

"хр равносильно Ø$хØр

$хр равносильно Ø"хØр

Теорема о перестановочности кванторов:

"х"ур равносильно "у"хр

$х$ур равносильно $у$хр

Типовые кванторы. Запись "_qхр обозначает высказывание "х(qÞр), а запись $_qхр обозначает высказывание $х(qÙр).

Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r₁ на высказывание r₂; тогда если r₁ и r₂ равносильны, то р и q тоже равносильны.

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

Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций Þ, Û и теорем об отрицании для операций ", $, Ø, Ù, Ú.

Пример построения позитивной формы отрицания высказывания: «для каждого положительного числа е существует положительное число d т.ч. для каждого числа х из х<d следует, что х<е или х£1».

Ø"е$d"х(х<dÞх<еÚх£1 = $e"d$хØ(х<dÞх<eÚх£1) = $e"d$хØ(Øх<dÚх<eÚх£1) = $e"d$х(х<dÙØх<eÙØх£1) = $e"d$х(х<dÙх³eÙх>1) = « существует положительное число е т.ч. для каждого положительного числа d существует число х т.ч. х<d и х³e и х>1».

Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р₀ является кванторологическим следствием из p₁,…,p_n тттк р₀ может быть получено из р₁,…,р_n с помощью этих шести правил:

Dt – правило тавтологии

Ds, sÞr, r – правило отделения

D"хрÞp{x, a} – правило обобщения

Dp{x, a} Þ$xp – правило подтверждения

DqÞr, qÞ"хr – правило общевнесения

DrÞq, $xrÞq – правило сущевнесения

где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n = 0.

Тема 5. Эгалитарная логика

или логика предикатов с равенством, т.е. с двухместным предикатным символом g²_0, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g²₀(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g

интерпретируется как знак равенства. Запись p₁, …, p_n│=q_{1, …}, q_m означает, что каждое из высказываний q_{1, …}, q_m является логическим следствием из высказываний p₁, …, p_n т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p₁, …, p_n. Высказывание p называется логически истинным, если │=p т.е. если p является истинным в любой эгалитарной интерпретации.