Логика. Все лекции

Лекция 3. Формулы логики высказываний. Тавтологии. Логические

следствия.

Пример 10. Построим		таблицу				истинности для формулы A Ù (B Ú C) .
	A		B	C				B Ú C			Ù (B Ú C)
						A				A
	1		1	1		0		1		0
	1		1	0		0		1		0
	1		0	1		0		1		0
	1		0	0		0		0		0
	0		1	1		1		1		1
	0		1	0		1		1		1
	0		0	1		1		1		1
	0		0	0		1		0		0

Пример	11.			Построим				таблицу	истинности			для	фо
(( A Þ B) Ù (B Þ C)) Þ ( A Þ C) .
		A	B		C	A Þ B	B Þ C	( A Þ B) Ù (B Þ C)	A Þ C	F
		1	1		1	1	1	1	1	1
		1	1		0	1	0	0	0	1
		1	0		1	0	1	0	1	1
		1	0		0	0	1	0	0	1
		0	1		1	1	1	1	1	1
		0	1		0	1	0	0	1	1
		0	0		1	1	1	1	1	1
		0	0		0	1	1	1	1	1

Мы замечаем ещё одну важную вещь. Высказывание, выражаемое приведенной формулой, принимает только значения "И" независимо от значений элементарных высказываний, входящих в формулу! Такие формулы называютсятождественно истинными (ТАВТОЛОГИЯМИ).

Следовательно, если сформировать отрицание этого высказывания, это даст тождественно ложную

(ПРОТИВОРЕЧИЕ) формулу ( в её таблице истинности последний столбец будет содержать все значения "Л") .

Определение 7. Формула называется тавтологией (тождественно истинной формулой), если она принимает значение 1 при всех наборах логических значений букв, которые в неё входят

Пример: см пример 11.

Определение 8. Формула называется противоречием (тождественно ложной формулой), если она принимает значение 0 при всех наборах логических значений букв, которые в неё входят

Пример 12: A Ù A

A

A

A Ù A

1

0

0

0

1

0

Из

примеров 11

и 12 видно,

что

все

формулы ЛВ

делятся на три класса: тождественно

ложные,

тождественно

истинные

и

не

принимающие

постоянного значения при измене

1

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

Встаёт вопрос: а не могут ли различные формулы иметь одинаковые таблицы истинности?

Иными словами: могут ли различные по форме сложные высказывания тем не менее одинаковыми по смыслу? Опыт обычных неформальных рассуждений подтверждает, что это так, поскольку само высказывание "А тогда и только тогда, когда В" не могло бы иначе возникнуть.

§3. ПРОВЕРКА РАВНОСИЛЬНОСТИ ФОРМУЛ ЛОГИКИ ВЫСКАЗЫВАНИЙ

Для установления основных равносильностей в самом деле не остаётся ничего иного, как

сравнение таблиц истинности формул. Проведём несколько таких сравнений.

СРАВНЕНИЕ 1. Рассмотрим высказывание ( A Þ B) Ù (B Þ A)

A	B	A Þ B	B Þ A	( A Þ B) Ù (B Þ A)
1	1	1	1	1
1	0	0	1	0
0	1	1	0	0
0	0	1	1	1

Из таблицы видно, что это высказывание истинно именно в тех случаях, когда значения А и В одинаковы. Но ведь именно так ведёт себя и связка A Û B ! Вывод: A Û B º ( A Þ B) Ù (B Þ A) .

А поскольку и простые логические переменные, и сложные формулы принимают всегда

значения И либо Л, то на самом деле справедлива более общая равносильность:

Ф1 Û Ф2 º (Ф1 Þ Ф2 ) Ù (Ф2 Þ Ф1)

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

СРАВНЕНИЕ 2. Рассмотрим высказывание A Ú B . Построив для него окончательную таблицу истинности, получим:

A	B
			A			A Ú B
1	1	0				1
1	0	0				0
0	1	1				1
0	0	1				1

Но ведь это таблица, отражающая картину поведения уже знакомой связки A Þ B ! Вывод очевиден:

A Þ B º A Ú B

И, конечно же, справедлива более общая равносильность

Ф1 Þ Ф2 º Ф1 Ú Ф2

А это означает, что и связка следования не обязательна для построения , фор выражающих смысл сложных высказываний: можно её исключить, всякий раз заменяя следование на равносильную конструкцию, содержащую только знаки связок "отрицание" и "или". В частности,

2

можно заметить, что связка эквивалентности равносильна высказыванию, содержащему только три связки: ¬ V ^ . Таким образом, эти логические связки являются основными, а остальные -

вспомогательными.

Далее мы рассмотрим таблицу основных равносильностей. Каждое её соотношение можно проверить так же, как мы сделали только что в СРАВНЕНИИ 1 и СРАВНЕНИИ 2.

ТАБЛИЦА ОСНОВНЫХ РАВНОСИЛЬНОСТЕЙ

Первая группа

Равносильности, показывающие возможность

выразить связки Û и Þ через

¬ V ^

1.

A Û B º ( A Ù B) Ú (

Ù

)

Выражение эквивалентности через ¬ V ^

B

A

2.

A Þ B º

Ú B

Выражение импликации через ¬ V

A

ВТОРАЯ ГРУППА

Равносильности, выражающие свойства отдельно

взятой основной связки

3.

Ø(ØA) º A

Закон двойного отрицания

4.

A Ù B º B Ù A

Переместительный закон для логического умножения

5.

( A Ù B) Ù C º A Ù (B Ù C)

Сочетательный закон для логического умножения

6.

A Ù A º A

7.

A Ù1 º A

Умножение на логическую единицу

8.

A Ù 0 º 0

Умножение на логический нуль

9.

A Ú B º B Ú A

Переместительный закон для логического сложения

10.

( A Ú B) Ú C º A Ú (B Ú C)

Сочетательный закон для логического сложения

11.

A Ú A º A

12.

A Ú1 º 1

Сложение с логической единицей

13.

A Ú 0 º A

Сложение с логическим нулём

ТРЕТЬЯ ГРУППА

Равносильности, выражающие отношения между

основными связками

14.

A Ú

º 1

Закон исключённого третьего

A

15.

A Ù

º 0

Закон противоречия

A

16.

º

Ù

Закон де Моргана

A Ú B

A

B

17.

º

Ú

Закон де Моргана

A Ù B

A

B

18.

( A Ú B) Ù C º ( A Ù C) Ú (B Ù C)

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

19.

( A Ù B) Ú C º ( A Ú C) Ù (B Ú C)

Второй распределительный закон

20.

( A Ú B) Ù A º A

Первый закон элементарного поглощения

21.

( A Ù B) Ú A º A

Второй закон элементарного поглощения

Пример 13. Доказать, что формулы ( A Þ B) Þ C и ( A Ú C) Ù (B Ú C) равносильны.

Доказательство. С одной стороны, дважды пользуясь равносильностью 2,

получим:

( A Þ B) Þ C º ( A Ú B) Þ C º A Ú B Ú C .

3

Теперь, используя закон 16, получим:

A Ú B Ú C º A Ù B Ú C ,

наконец, пользуясь законом двойного отрицания 3, получаем:

A Ù B Ú C º A Ù B Ú C .

Итак, ( A Þ B) Þ C º A Ù B Ú C .

С другой стороны, в силу распределительного закона 19, для второй формулы имеем:

	( A Ú C) Ù (B Ú C) º A Ù B Ú C .
Так как обе исходных формулы		оказались		равносильны одной		и той
формуле, они сами равносильны.
Между понятием равносильности и логической связкой эквивалентности можно заметить
тесную связь: если формулы	Ф1 º Ф2 (равносильны), то формула Ф1 Û Ф2				является тождественно
истинной, и наоборот, если	доказано, что Ф1 Û Ф2		тождественно истинна, то Ф1 º Ф2 : они всегда
принимают одинаковые значения при заданных значениях входящих в них						элемента
высказываний.
Таким образом, проверить, являются		ли	две формулы логики		высказыванийФ	и Ф
					1	2
равносильными, можно ещё одним способом: определяя,				является ли	тождественно истинной
формула Ф1 Û Ф2 .

§4.ОСНОВНЫЕ ТАВТОЛОГИИ, НЕКОТОРЫЕ ПРИМЕНЕНИЯ ТАВТОЛОГИЙ

4

§5. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ
Определение 9. Формула B называется логическим следствием										формул A1, ..., An , если для всех
наборов значений букв, которые входят в A1, ..., An						и B , значение B есть 1 каждый раз, когда
значение каждой формулы Ai , i =		на этом наборе есть 1. Обозначается A1,..., An a B .
	1, n
Пример 14. Покажем, что B является						логическим				следствием формул A и
A Þ B , т.е. A, A Þ B a B .
Решение. Построим таблицу истинности для формул A,							A Þ B, B .
			A	B	A Þ B			B
			1	1	1			1
			1	0	0			0
			0	1	1			1
			0	0	1			0

Красным цветом выделены столбцы для формул из посылки, а синим – для следствия. Согласно определения, необходимо проверить, чтобы во всех строках, где одновременно встречаются две красные единицы синей была также1, а не 0 (эта строка выделена жирным шрифтом). Таким образом, мы убедились, что B является логическим следствием формул A и A Þ B .

Пример 15. Проверить справедливость следующих рассуждений: «Сегодня я пойду в кино на новую кинокомедию или на занятия в университет. Если я

пойду в кино, то я три часа буду смеяться. Если	я пойду на занятия, то
я получу много новых знаний. Значит, сегодня я	три часа буду смеяться
или получу много новых знаний.»

Решение. Рассмотрим следующие высказывания:

А= «Я пойду в кино»

В= «Я пойду на занятия в университет» C = «Я три часа буду смеяться»

D = «Я получу много новых знаний».

Итак, нам необходимо проверить, что ( A Ú B, A Þ C, B Þ D) a(C Ú D) . Построим таблицу истинности.

A	B	C	D	A Ú B			A Þ C			B Þ D			C Ú D
1	1	1	1		1			1			1			1
1	1	1	0		1			1			0			1
1	1	0	1		1			0			1			1
1	1	0	0		1			0			0			0
1	0	1	1		1			1			1			1
1	0	1	0		1			1			1			1
1	0	0	1		1			0			1			1
1	0	0	0		1			0			1			0
0	1	1	1		1			1			1			1
0	1	1	0		1			1			0			1
0	1	0	1		1			1			1			1
0	1	0	0		1			1			0			0
0	0	1	1		0			1			1			1
0	0	1	0		0			1			1			1
0	0	0	1		0			1			1			1
0	0	0	0		0			1			1			0

5

Строки, в которых одновременно встречаются три красные единицы выделены желтым цветом. Как видим, во всех этих строках в синем столбце также стоит единица. Значит, рассуждение верно.

Второй способ решения. Допустим, что формула C Ú D не является логическим следствием

формул A Ú B , A Þ C ,										B Þ D .		Значит,			при некоторых значениях букв A, B,C, D																каждая из формул
A Ú B , A Þ C ,						B Þ D принимает значения 1, а формула C Ú D - значение 0.
1). Т.к. (C Ú D) = 0 , то (C) =), (D) = 0 .
2). Т.к. ( A Þ C) = 1, (C) = 0 , то ( A) = 0 .
3). Т.к. (B Þ D) = 1, (D) = 0 , то (B) = 0 .
4). Но если (B) = 0, ( A) = 0 , то ( A Ú B) = 0 .
		Полученное противоречие показывает,														что формула C Ú D									является логическим следствием
формул			A Ú B , A Þ C ,							B Þ D .
Пример 16. Выяснить, является																ли		препозиционная											формула			логическим
следствием предыдущих формул															( A Ù B) Þ C, (C Ù D) Þ E,								Þ (D Ù E)				a ( A Ù B) Þ F .
																						F
Решение.				Допустим						противное:				формула		( A Ù B) Þ F					не				является				логическим				следствием
предыдущих формул. Значит, (( A Ù B) Þ F ) = 0 .
1). (( A Ù B) Þ F ) = 0 , тогда (F ) = 0, ( A Ù B) = 1 , т.е. (F ) = 0, ( A) = 1, (B) =1 .
2). ( A) = 1, (B) = 1, (( A Ù B) Þ C) = 1 , значит (C) = 1 .
3). (F ) = 0 , значит (									) = 1 .
								F
4). (		) = 1, (			Þ (D Ù E)) = 1 , значит (D Ù E) = 1 , т.е. (D) = 1,(E) = 1 .
	F			F
		Итак,				при			( A) = (B) = (C) = (D) = (E) = 1, (F ) = 0										формула (( A Ù B) Þ F ) = 0 ,												а	все	посылки
принимают						значение 1. Значит,								формула			( A Ù B) Þ F				не				является				логическим				следствием
предыдущих формул.
Пример 17. Выяснить, является																ли		препозиционная											формула			логическим
следствием предыдущих формул
(1) A Þ B, B Þ C a A Þ C . Да, является.
											A	B	C		A Þ B		B Þ C			A Þ C
											1	1		1	1		1			1
											1	1		0	1		0			0
											1	0		1	0		1			1
											1	0		0	0		1			0
											0	1		1	1		1			1
											0	1		0	1		0			1
											0	0		1	1		1			1
											0	0		0	1		1			1
(2) ( A Ú B) Þ (C Ú B)							a A Þ C . Нет, не является
											A	B	C		A Ú B	B Ú C			( A Ú B) Þ (C Ú B)								A Þ C
											1	1		1	1	1					1							1
											1	1		0	1	1					1							0
											1	0		1	1	1					1							1
											1	0		0	1	0					0							0
											0	1		1	1	1					1							1

6

0			1	0	1	1	1	1
0			0	1	0	1	1	1
0			0	0	0	0	1	1

(3) A Þ B, D Þ C, C Ú B a A Þ D . Да, является

A	B	C	D	A Þ B	D Þ	C		C Ú	B		A Þ	D
1	1	1	1	1	0			1			0
1	1	1	0	1	1			1			1
1	1	0	1	1	1			0			0
1	1	0	0	1	1			0			1
1	0	1	1	0	0			1			0
1	0	1	0	0	1			1			1
1	0	0	1	0	1			1			0
1	0	0	0	0	1			1			1
0	1	1	1	1	0			1			1
0	1	1	0	1	1			1			1
0	1	0	1	1	1			0			1
0	1	0	0	1	1			0			1
0	0	1	1	1	0			1			1
0	0	1	0	1	1			1			1
0	0	0	1	1	1			1			1
0	0	0	0	1	1			1			1

Пример 18. Если Джонс не встречал сегодня Смита, то либо Смит убийца, либо

Джонс обманывает. Если	Смит	не убийца, тогда Джонс не встречал сегодня Смита,
и убийство произошло	после	полуночи. Если убийство произошло после полуночи,

то либо Смит убийца, либо Джонс обманывает. Значит, Смит – убийца. Является ли логически правильным это рассуждение?

А= «Джонс не встречал Смита», В= «Смит убийца», С= «Джонс лжет»,										D = «Убийство произошло после
полуночи»
	A	B	C	D	A Þ (B Ú C)	B Ú (		Ù D)	D Þ (C Ú B)		B
							A
	1	1	1	1	1	1			1		1
	1	1	1	0	1	1			1		1
	1	1	0	1	1	1			1		1
	1	1	0	0	1	1			1		1
	1	0	1	1	1	1			1		0
	1	0	1	0	1	0			1		0
	1	0	0	1	0	1			0		0
	1	0	0	0	0	0			1		0
	0	1	1	1	1	1			1		1
	0	1	1	0	1	1			1		1
	0	1	0	1	1	1			1		1
	0	1	0	0	1	1			1		1
	0	0	1	1	1	1			1		0
	0	0	1	0	1	0			1		0
	0	0	0	1	1	1			0		0
	0	0	0	0	1	0			1		0

Рассуждение не верно.

7

Пример 19. "Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

-Говорит Мегрэ. Есть новости?

-Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если

Франсуа был пьян, то или Этьен убийца, или Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи.

Инспектор	Люка просил	передать	,Вамчто если убийство произошло	после
полуночи,	то или Этьен убийца, или Франсуа лжет. Затем звонила...			что
- Все.	Спасибо. Этого	достаточно.-	Комиссар положил трубку. Он знал,

трезвый Франсуа никогда не лжет. Теперь он знал все."

Что следует из показаний инспекторов? Какой вывод сделал комиссар Мегрэ?

А= «Франсуа был		пьян»,				В=		«Этьен		убийца»,		С= «Франсуа лжет», D =					«Убийство произошло после
полуночи»
	A	B			C		D		A Þ (B Ú C)			B Ú (		Ù D)	D Þ (C Ú B)			Þ
													A				A		C
	1		1			1		1		1		1			1		1
	1		1			1		0		1		1			1		1
	1		1			0		1		1		1			1		1
	1		1			0		0		1		1			1		1
	1	0				1		1		1		0			1		1
	1	0				1		0		1		0			1		1
	1	0				0		1		0		0			0		1
	1	0				0		0		0		0			1		1
	0		1			1		1		1		1			1		0
	0		1			1		0		1		1			1		0
	0		1			0		1		1		1			1		1
	0		1			0		0		1		1			1		1
	0	0				1		1		1		1			1		0
	0	0				1		0		1		0			1		0
	0	0				0		1		1		1			0		1
	0	0				0		0		1		0			1		1

Этьен убийца.

8

Тема 3: Предикаты. Кванторы.

Лекция 4. Предикаты. Кванторы общности и существования.

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

Валгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

Ни структура высказываний, ни, тем более, их содержание не затрагиваются. В то же время

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

Например, в рассуждении “Всякий ромб – параллелограмм; АВСD – ромб; следовательно, АВСD - параллелограмм” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Такой логической системой являетсяЛОГИКА ПРЕДИКАТОВ, содержащая всю логику высказываний в качестве своей части.

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

Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте.

Пример	1.	В высказывании	“7 - простое	число”, “7”	– субъект, “простое
число”	–	предикат. Это	высказывание	утверждает,	что	“7” обладает
свойством “быть простым числом”.

Если в рассмотренном примере заменить конкретное число7 переменной x из множества натуральных чисел, то получим высказывательную форму “ x –простое число”. При одних значения x (например, x = 13 , x = 17 ) эта форма дает истинные высказывания, а при других значениях x (например, x = 10 , x = 18 ) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменнойx , определенной на множестве À , и принимающую значения из множества {1; 0} . Здесь предикат становится

функцией субъекта и выражает свойство субъекта.

Дадим несколько определений, относящихся к предикатам.

Определение 1. Одноместным предикатом P(x) называется произвольная функция переменного

x , определенная на множестве M и принимающая значение из множества {1; 0} .

Определение 2. Множество M , на котором определен предикат P(x) , называется областью опре-

деления предиката P(x) ).

Определение 3. Множество всех элементов x Î M , при которых предикат принимает значения “ис-

тина” (1), называется множеством (областью) истинности предиката P(x) , т.е. множество ис-

тинности предиката P(x) - это множество I p = {x : x Î M , P(x) = 1}, или иначе: M [P] или так: M [P(x)]. x x

1

Пример 2. Предикат	P(x) =“ x – простое число” определен на множестве À , а
множество истинности I p для него есть множество всех простых чисел.
Пример 3. Предикат	Q(x) =“sin x = 0 ” определен на множестве R , а	его множе-
ством истинности является IQ = {kp , k Î Z}.
Пример 4. Предикат	F (x) =“диагонали параллелограмма x взаимно	перпенди-

кулярны” определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Упражнение 1. Найти множество истинности следующих предикатов, определенный на R :

а). x2 - 4 = 0 ( I = {-2; 2} )

б). x2 + 4 = 0 ( I = Æ )

в). x2 + 4x + 4 = 0 ( I = {2} ).

Из приведенных примеров видим, что одноместные предикаты выражают свойства предме-

тов (субъектов).
Определение 4. Предикат P(x) , определенный на множестве M ,	называется тождественно ис-
тинным, если его множество истинности совпадает с областью определения, т. е. I p = M .
Пример 5. Предикат P(x) = «| x |³ 0 », определенный на	R , тождественно истин-
ный.

Предикат P(x, y) =	«(x + y)2 = x2 + 2xy + y2 »,	определенный на	R2 , тождествен-
но истинный.
Определение 5. Предикат	P(x) , определенный на	множестве M , называется тождественно
ложным, если его множество истинности является пустым множеством, т. е.			I p = 0 .
Пример 6. Предикат P(x) = «| x |< 0 » - тождественно ложный на			R .

Естественным обобщением понятия одноместного предиката является понятие многомес-т ного предиката, с помощью которого выражаются отношения между предметами.

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множествеZ целых чисел. Оно может быть охарактеризовано высказывательной формой “ x < y ”, где x, y Î Z , т. е. является функцией двух пе-

ременных P(x, y) , определенной на множестве упорядоченных пар целых чисел Z ´ Z = Z 2 c множе-

ством значений {1;0}.

Определение 6. Двухместным предикатом P(x, y) называется функция двух переменных x и y ,

определенная на множестве M = M1 ´ M 2 и принимающая значения из множества {1;0}.

Пример 7. Q(x, y) = “ x = y ” -	предикат	равенства, определенный	на множестве
R ´ R = R2 ;	“прямая x	параллельна прямой y ”,	определенный
F (x, y) =“ x параллелен y ”,

на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката.

Пример	8.	S (x, y, z) =“ x + y = z ”. Подстановка	в	него x = 3 превращает			его в
двухместный		предикат: S ( y, z) =“3 + y = z ”, а	подстановка		x = 3 , z = 2	– в	одно-
местный	предикат S ( y) =“3 + y = 2 ”.Подстановка же			S (2,3,5)	превращает	его	в ис-
тинное высказывание, а S (1,7,4) – в ложное.
Аналогично определяется и n -местный предикат (функция n переменных).

2