Правила выводов логики высказываний

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

Вариант 0

1. Вопрос по теории.

2. Обладает ли эйлеровой цепью (или эйлеровым циклом) следующий граф?

3. Является ли данный граф плоским? (планарным)

4. Считая данный граф планарным, определить количество его граней.

5. Дан граф:

Найти кратчайший путь из точки в точку В (в смысле наименьшего количества рёбер).

6. Дан граф.

B

A

а) Превратить его во взвешенный, используя следующие данные

б) Найти кратчайший путь из точки в точку В (в смысле наименьшей суммы весов).

7. Найти хроматическое число графа

Логика высказываний – это логическая система, которая анализирует процессы рассуждения, опираясь на истинностные характеристики логических связок и отвлекаясь от внутренней структуры суждений.

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

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

Правила вывода записываются в виде схемы, которая состоит из двух частей (верхней и нижней), разделенных горизонтальной линией – над чертой выписываются логические схемы посылок, под ней – заключение.

Схема правил вывода:

Читается: из посылок вида А1, А2, А3...Ап можно вывести заключение В.

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

Выводом в P_N называется конечная последовательность выражений, каждое из которых есть либо 1) посылка, либо 2) доказанная штопор-формула, либо 3) получается из предыдущих выражений последовательности по одному из правил вывода системы P_N; при этом последнее выражение последовательности должно быть получено либо по пункту 2, либо по пункту 3.

Последнее выражение вывода – это его заключение.

Основные правила – более простые и очевидные.

Производные выводятся из основных. Их введение сокращает процесс вывода.

Как основные, так и производные делятся на прямые и непрямые (косвенные)

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

Непрямые (косвенные) правила выводов дают возможность заключить о правомерности некоторых выводов из правомерности других выводов.

В языковой практике люди (исследователи) имеют какие-то высказывания (знания) x, обладают какими-то навыками оперирования высказываниями, в том числе - навыками получения из данных высказываний новых высказываний y. В логике как науке, изучающей такого рода явления, это запишется (зафиксируется) в высказывании «Из " x" выводится (логически следует, дедуцируется) " y"». В этом высказывании слово «выводится» («логически следует», «дедуцируется») является предикатом, а не логическим оператором. Вместо него для краткости и стандартности может быть введен особый значок, например (как это делаю я) – значок ├. Повторяю и подчеркиваю: это - не оператор, а термин, причем – именно предикат. В логике обычно этот факт игнорируют и используют в качестве предиката следования (вывода) логический оператор, называемый импликацией. Это порождает путаницу и мешает пониманию сути дела. С упомянутым значком тот факт, что из высказывания x выводится высказывание y, можно для краткости записать символом x├ y. В этом высказывании терминами являются выражения «Высказывание x» и «Высказывание y». Они суть метатермины по отношению к " x" и " y", т.е. термины, обозначающие высказывания, состоящие из терминов. В логике этот факт точно так же игнорируется, поскольку знак вывода (следования) рассматривается как оператор. Это усугубляет путаницу. В результате проблема правил вывода вообще сводится к операторам «логики высказываний» (к функциям исчисления высказываний). Достаточно детальное решение возникающих здесь проблем дано в моей работе «Логическое следование» (помещена в сборник «Очерки комплексной логики», упомянутый во Введении).

Итак, формула x├ y есть лишь краткая и стандартизированная запись высказывания о том, что из высказывания "x" выводится по особым логическим правилам высказывание "y". Если вывод осуществляется из двух или более высказываний x 1,..., x n, то эти высказывания можно рассматривать как конъюнкцию, т.е. как одно высказывание «x 1 и... и x n». И такие случаи сводятся к общему выражению x├ y. При этом высказывание "x" называется посылкой вывода (умозаключения), а высказывание "y" называется заключением или следствием.

Формула x├ y (Из x следует y) фиксирует связь высказываний "x" и "y", а не связь предметов, о которых говорится в высказываниях. В каких логических структурах фиксируются связи предметов, об этом речь пойдет в дальнейшем (в разделе «Онтология»). Какие именно связи высказываний имеются в виду, этому и посвящается логическая теория вывода (логического следования).

Правила вывода вырабатываются с таким расчетом, чтобы выполнялся следующим принцип дедукции: если высказывание y по этим правилам получается из высказываний x 1,..., x n, и последние считаются истинными, то и y должно признать истинным.

При построении исчисления прежде всего

· приводится совокупность знаков, которые будут фигурировать в нем (их называют алфавитом), и

· дается определение их комбинаций, подлежащих рассмотрению (их называют формулами).

· Затем излагаются аксиомы (или аксиомные семы) и

· правила вывода теорем из аксиом.

· Дается определение доказуемой формулы. В число таковых включаются аксиомы и теоремы. В моих построениях заранее предполагается, что алфавит фиксирует языковые объекты, подлежащие логической обработке, – логические операторы и конструируемые с ними высказывания и термины.

· Плюс к тому – логические термины – знаки логических терминов «субъект», «предикат», «выводится» («логически следует»), «логически истинно», «доказуемо», «включается по значению», «тождественно по значению», «дедуктивно эквивалентно» и т.д. В логике обычно логические термины путаются с логическими операторами. Например, на роль предиката вывода (следования) выбирается одна из функций логики высказываний – импликация. Доказуемые формулы заранее планируются на роль описания правил вывода (следования, умозаключения).

Основныеправила:

прямые …..

непрямые..

введения и удаление конъюнкции

введения и удаления дизъюнкции

Удаления импликации

введения и удаления эквиваленции

введения и удаления двойного отрицания

Введения импликации и сведения к абсурду

В.К.	У.К.
А В	А∧ В	А∧ В
А∧ В	А	В

В.Д.	У.Д.
А (В)	А ∨ В	А ∨ В
А ∨ В	Ā	В
	В	А

У.И.

А → В

А

В

В.Э.	У.Э.
А→ В	А↔ В	А↔ В
В→ А	А→В	В → А
А↔ В

В.О.	У.О.
А	А
А	А

В.И.	С.А.
П (посылки)	П (посылки)
А(доп.)	А(доп.)
……	…….
…….	…….
…….	В
В	В
А→ В	А

Производные правила

Правило условного силлогизма

Правило modus tollens

Правило отрицания дизъюнкции (ОД)

Правило	Доказательство
А→ В	А→ В	1.	Посылка
В → С	В →С	2.	Посылка
А→ С	А	3.	Допущение
	В	4.	У.И. 1, 3.
	С	5.	У.И. 2, 4.
	А→ С	6.	В.И. 3, 5

Правило	Доказательство правила:
А → В		А → В	Посылки
В		В	Посылки
А		А	Допущение
		В	У.И.1,3.
		А	С.А. 2,4

Правило	Доказательство:
(А∨В)		(А∨В)	Посылка
А∧В		А	Допущение
		А∨В	В.Д.2
		А	С.А.1.3
		В	Допущение
		А∨В	В.Д.5
		В	С.А.1.6
		А∧В	В.К. 4, 7

Правило отрицания конъюнкции (ОК)

Правило	Доказательство:
(А∧В)		(А∧В)	Посылка
А∨В		(А∨В)	Допущение
		А∧В	О.Д.2
		А	У.К.3
		А	У.О.4
		В	У.К.3
		В	У.О.6
		А∧В	В.К.5.7
		(А∨В)	С.А.1,8
		А∨В	У.О.9

Правила контрапозиции 1

Правила контрапозиции:	Доказательство
А → В		А → В	Посылка
В→А		В	Допущение
		А	M.t.1,2
		В→А	В.И.2,3

Правила контрапозиции 2

2 Правило	Доказательство
В→А		В→А	Посылка
А → В		А	Допущение
		А	В.О.2
		В	M.t. 1,3
		В	У.О.4
		А → В	В.И. 2,5

Правило сложной контрапозиции

Правило простой конструктивной дилеммы (П.К.Д.)

Правило:	Доказательство:
(А∧В)→С		(А∧В)→С	Посылка
(А∧С)→В		А∧С	Допущение
		А	У.К.2
		С	У.К.2
		(А∧В)	M.t.1,4
		А∨В	О.К.5
		А	В.О.3
		В	У.Д.6,7
		(А∧С)→В	В.И.2,8

Правило	Доказательство:
А→С		А→С	Посылка
В →С		В →С	Посылка
А∨В		А∨В	Посылка
С		С	Допущение
		А	M.t.1,4
		B	M.t.2,4
		B	У.Д.3,5
		С	С.А.6.7

Правило сложной конструктивной дилеммы (С.К.Д.)

Правило простой деструктивной дилеммы (П.Д.Д.)

Правило	Доказательство:
А→В		А→В	Посылка
С→D		С→D	Посылка
А∨C		А∨C	Посылка
В ∨D		A	Допущение
		В	У.И.1,4
		В∨D	В.Д. 5
		A →(В∨D)	В.И.4,6
		С	Допущение
		D	У.И.2,8
		B∨D	В.Д.9
		С →(B∨D)	В.И.8,10
		B∨D	Сведение к П.К.Д. 3,7,11

 

Правило	Доказательство:
А→В		А→В	Посылка
А→С		А→С	Посылка
В ∨С		В ∨С	Посылка
А		В→А	Правило контрапозиции. 1
		С→А	Правило контрапозиции. 2
		А	П.К.Д. 3,4,5

Правило сложной деструктивной дилеммы (С.Д.Д.)

Правило	Доказательство:
А→В		А→В	Посылка
С→D		С→D	Посылка
В ∨D		В∨D	Посылка
А ∨С		В→А	П.К.1
		D→С	П.К.2
		А∨С	С.К.Д.3,4,5

1. Упражнение: восстановите анализ доказательства

Производные правила

Правило условного силлогизма

Правило modus tollens

Правило отрицания дизъюнкции (ОД)

Правило	Доказательство
А→ В	А→ В	1.	…………
В → С	В →С	2.	…………
А→ С	А	3.	…………
	В	4.	…………
	С	5.	…………
	А→ С	6.	…………

Правило	Доказательство правила:
А → В		А → В	…………
В		В	…………
А		А	…………
		В	…………
		А	…………

Правило	Доказательство:
(А∨В)		(А∨В)	…………
А∧В		А	…………
		А∨В	…………
		А	…………
		В	…………
		А∨В	…………
		В	…………
		А∧В	…………

Правило отрицания конъюнкции (ОК)

Правило	Доказательство:
(А∧В)		(А∧В)	…………
А∨В		(А∨В)	…………
		А∧В	…………
		А	…………
		А	…………
		В	…………
		В	…………
		А∧В	…………
		(А∨В)	…………
		А∨В	…………

Правила контрапозиции 1

Правила контрапозиции:	Доказательство
А → В		А → В	…………
В→А		В	…………
		А	…………
		В→А	…………

Правила контрапозиции 2

2 Правило	Доказательство
В→А		В→А	…………
А → В		А	…………
		А	…………
		В	…………
		В	…………
		А → В	…………

2. Упражнение: восстановите анализ доказательства

Правило сложной контрапозиции

Правило простой конструктивной дилеммы (П.К.Д.)

Правило:	Доказательство:
(А∧В)→С		(А∧В)→С	…………
(А∧С)→В		А∧С	…………
		А	…………
		С	…………
		(А∧В)	…………
		А∨В	…………
		А	…………
		В	…………
		(А∧С)→В	…………

Правило	Доказательство:
А→С		А→С	…………
В →С		В →С	…………
А∨В		А∨В	…………
С		С	…………
		А	…………
		B	…………
		B	…………
		С	…………

Правило сложной конструктивной дилеммы (С.К.Д.)

Правило простой деструктивной дилеммы (П.Д.Д.)

Правило	Доказательство:
А→В		А→В	…………
С→D		С→D	…………
А∨C		А∨C	…………
В ∨D		A	…………
		В	…………
		В∨D	…………
		A →(В∨D)	…………
		С	…………
		D	…………
		B∨D	…………
		С →(B∨D)	…………
		B∨D	…………

 

Правило	Доказательство:
А→В		А→В	…………
А→С		А→С	…………
В ∨С		В ∨С	…………
А		В→А	…………
		С→А	…………
		А	…………

Правило сложной деструктивной дилеммы (С.Д.Д.)

Правило	Доказательство:
А→В		А→В	…………
С→D		С→D	…………
В ∨D		В∨D	…………
А ∨С		В→А	…………
		D→С	…………
		А∨С	…………

1 таблица

№	Пример	Пример	Осн/неосн	Прямые/ непрямые	Простые /сложные	Непоср/ опосред	схемы	Название
1.	А В	А В А∧ В	Осн	прям	прост	Непоср	A, B ├ A & B	В.К.
2.	А∧ В	А∧ В А	Осн	прям	прост	Непоср	A & B ├ A	У.К.
3.	А∧ В	А∧ В В	Осн	прям	прост	Непоср	A & B ├ B	У.К.
4.	А (В) А ∨ В	А (В) А ∨ В	Осн	прям	прост	опоср	A, B ├ A ∨ B	В.Д
5.	А ∨ В Ā …..	А ∨ В Ā В	Осн	прям	прост	опоср	A ∨ B, Ø B ├ A	У.Д.
6.	А ∨ В ….. А	А ∨ В В А	Осн	прям	прост	опоср	A ∨ B., Ø A ├ B	У.Д.
7.	А → В А …..	А → В А В	Осн	прям	прост	опоср	A É B, A ├ B	У.И.	Если у человека повышенная температура, он болен. У человека повышенная температура Человек болен.
8.	А→ В В→ А …..	А→ В В→ А А↔ В	Осн	прям	прост	опоср	A É B,BÉ A ├A ↔ B	В.Э.
9.	А↔ В …..	А↔ В А→В	Осн	прям	прост	Непоср.	A ↔ B B ├ A É	У.Э.
10.	А↔ В …..	А↔ В В → А	Осн	прям	прост	Непоср.	A ↔ B B ├BÉ A	У.Э.
11.	А …..	А А	Осн	прям	прост	Непоср.	A ├ Ø Ø A	В.О
12.	А …..	А А	Осн	прям	прост	Непоср.	Ø Ø A ├ A	У.О.
13.	П (посылки) А(доп.) …… ……. ……. В …..	П (посылки) А(доп.) …… ……. ……. В А→ В	осн	Непрямые правила	сложной	Опоср	П (пос), A(доп)…B ├ A É B	В.И.
14.	П (посылки) А(доп.) ……. ……. В В …..	П (посылки) А(доп.) ……. ……. В В А	осн	Непрямые правила	прост	Опоср	П (пос), A(доп)…B, Ø B, ├ A ÉB	С.А.
15.	А→ В В → С …..	А→ В В → С А→ С	Производные правила	-	сложной	Опоср	A É B, B É C ├ A ÉC	Правило условного силлогизма
16.	А → В В …..	А → В В А	Производные правила	-	прост	Опоср	A É B, Ø B ├ Ø A	Правило modus tollens	Если гелий — металл, он электропроводен. Гелий неэ лектропроводен. Гелий — не металл.
17.	(А∨В) …..	(А∨В) А∧В	Производные правила	-	сложной	непоср	Ø (A Ú B) ├ Ø A & Ø B	Правило отрицания дизъюнкции (ОД)
18.	(А∧В) …..	(А∧В) А∨В	Производные правила	-	сложной	непосредсв	Ø (A & B) ├ Ø A Ú Ø B	Правило отрицания конъюнкции(закон де Моргана) (ОК)
19.	А → В …..	А → В В→А	Производные правила	-	сложной	непосредсв	A É B ├ Ø B É Ø A	Правило контрапозиции 1
20.	В→А …..	В→А А → В	Производные правила	-	сложной	непосредсв	Ø B É Ø A ├ A É B	Правило обратной контрапозиции 2
21.	(А∧В)→С …..	(А∧В)→С (А∧С)→В	Производные правила	-	сложной	непосредсв	(A & B) É C ├ (A & Ø C) É Ø B	Правило сложной контрапозиции
22.	А→С В →С А∨В …..	А→С В →С А∨В С	Производные правила	-	прост	Опоср	A É C, B É C, A Ú ├ C	Правило простой конструктивной дилеммы (П.К.Д.)
23.	А→В С→D А∨C …..	А→В С→D А∨C В ∨D	Производные правила	-	сложной	Опоср	A É C, B É D, A Ú B ├ C Ú D	Правило сложной конструктивной дилеммы (С.К.Д.)
24.	А→В А→С В ∨С …..	А→В А→С В ∨С А	Производные правила	-	прост	Опоср	A É B, A É C, Ø B Ú Ø C ├ Ø A	Правило простой деструктивной дилеммы (П.Д.Д.)
25.	А→В С→D В ∨D …..	А→В С→D В ∨D А ∨С	Производные правила	-	сложной	Опоср	A É B, C É D, Ø B Ú Ø D ├ Ø A Ú Ø C	Правило сложной деструктивной дилеммы (С.Д.Д.)

Упражнение

Дата добавления: 2014-11-25