Основные схемы логически правильных рассуждений

Оглавление

  Предисловие                                                                                            4

 

1. Логика высказываний                                                                           5

1.1. Основные понятия                                                                        5

1.2. Основные схемы логически правильных рассуждений    8

1.3. Алгебра логики                                                                             11

1.4. Булева алгебра                                                                             14

 1.5. Эквивалентные преобразования                                             18

1.6. Булева алгебра и теория множеств                                        27

2. Логика предикатов                                                                                35

2.1. Основные понятия                                                                        35

2.2. Кванторы                                                                                        37

2.3. Выполнимость и истинность                                                    39

2.4. Эквивалентные соотношения                                                   42

3. Вопросы коллоквиума “Введение в математическую логику” 47

 

  Список литературы                                                                               49

 

Предисловие

 

Настоящее методическое пособие призвано восполнить имеющийся пробел в учебной литературе по курсу “Дискретная математика”, в частности – практикум в решении задач по математической логике.

Рассматриваются традиционные разделы: логика высказываний и логика предикатов.

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

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

Материал практикума предоставляет возможность студентам самостоятельно освоить основные положения курса “Дискретная математика” (Ч. II. Введение в математическую логику), приобрести и закрепить практические навыки решения задач.

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

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

 

 

1. ЛОГИКА ВЫСКАЗЫВАНИЙ. [1]

Основные понятия.

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

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

Высказывание называется простым (элементарным), если оно рассматривается как некое неделимое целое. Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.

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

Пусть P, Q Î{ и,л }, где P, Q – простые высказывания, принимающие одно из двух значений: и – “истина”, л – “ложь”.

 

Таблица 1.1.1
P	Ø P
и	л
л	и

Ø P () – отрицание (инверсия) высказывания P.

 

Таблица 1.1.2
P	Q	P & Q	P Ú Q	P ® Q	P ~ Q	P Å Q
л	л	л	л	и	и	л
л	и	л	и	и	л	и
и	л	л	и	л	л	и
и	и	и	и	и	и	л
		1	2	3	4	5

 

1) P & Q (P Ù Q, P × Q) – конъюнкция (операция “и”, логическое произведение) высказываний P, Q;

2) P Ú Q – дизъюнкция (операция “или”, логическое сложение) высказываний P, Q;

 

3) P ® Q (P É Q) – импликация (логическое следование) высказываний P, Q (читается: “если P, то Q ”);

4) P ~ Q (P º Q, P «Q) – эквивалентность (эквиваленция, равнозначность) высказываний P, Q (читается: “ P, если и только, если Q ”);

5) P Å Q (P ∆ Q) – неравнозначность (сложение по mod 2) высказываний P, Q (читается: “либо P, либо Q ”; “или P, или Q ”).

Выражение, составленное из обозначений высказываний, логических связок (и, возможно, скобок), назовем логической формулой, если оно удовлетворяет следующим условиям:

– переменная, обозначающая высказывание, – элементарная (атомарная) формула;

– если P и Q – формулы, то (P & Q), (P Ú Q), (Ø P), (P ® Q), (P ~ Q), (P Å Q) – формулы;

– других формул нет.

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

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

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

Сравнить логические формулы и сделать выводы.

1. Первое составное высказывание состоит из следующих простых:

X – “Допоздна работаешь с компьютером”.

Y – “Пьешь много кофе”.

Z – “Утром встаешь в дурном расположении духа”.

U – “Утром встаешь с головной болью”.

Тогда логическая формула первого составного высказывания:

(X & Y)®(Z Ú U)

2. Второе составное высказывание состоит из следующих простых:

X – “Социологические исследования показывают, что потребитель отдает предпочтение удобству”.

Y – “Социологические исследования показывают, что потребитель отдает предпочтение многообразию выбора”.

Z – “Фирме следует сделать упор на усовершенствование товара”.

U – “Фирме следует сделать упор на увеличение многообразия новых форм”.

Логическая формула второго составного высказывания:

(X & Y)®(Z Ú U).

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

Пример 2. Записать формулами логики высказываний два способа доказательства равенства множеств, вытекающих из определений 1 и 2 равенства множеств X, Y.

Определение 1. “ X = Y, если из того, что a Î X, следует a Î Y, и из того, что a Ï X, следует, что a Ï Y ”.

Определение 2. “ X = Y, если из того, что a Î X, следует a Î Y, и из того, что a Î Y, следует, что a Î X ”.

Обозначим простые высказывания:

A:=“ a Î X ”;

B:=“ a Î Y ”;

C:=“ X = Y ”.

Тогда процедура доказательства X = Y:

а) для определения 1: ((A ® B)&(Ø A ®Ø B))®C;

б) для определения 2: ((A ® B)&(B ® A))®C;

Вопросы для самопроверки и упражнения.

 

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

а) (((A Ú B)®Ø C) ~ D)&((A Å C)®Ø D).

б) ((A ÅØ B)® C) ~ (D &® B).

2. Записать логической формулой следующий текст:

“Если компьютер при запуске не выдает ошибку при проверке оперативной памяти, то она исправна. Если при запуске он выдает ошибку при проверке оперативной памяти и память установлена правильно, то либо оперативная память дефектна, либо дефектна материнская плата. Тогда если эта оперативная память установлена в другой (контрольный) компьютер и он при запуске не выдает ошибку при проверке оперативной памяти, то оперативная память исправна”.

3. Записать логической формулой следующую пословицу:

“Не ел – не мог, поел – без ног”.

4. Составить таблицы Кэли для основных логических связок – бинарных логических операций.

 

 

Основные схемы логически правильных рассуждений.

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

Основные схемы логически правильных рассуждений:

1. Правило заключения – утверждающий модус (Modus Ponens):

A ® B, A

B

2. Правило отрицания – отрицательный модус (Modus Tollens):

A ® B, Ø B

Ø A

3. Правила утверждения–отрицания (Modus Ponendo–Tollens):

A Å B, A       A Å B, Ø B

Ø B                 Ø A

4. Правила отрицания–утверждения (Modus Tollen–Ponens):

а)       A Å B, Ø A          A Å B, Ø B

           B                   A

б)       A Ú B, Ø A           A Ú B, Ø B

B                    A

5. Правило транзитивности (упрощенное правило силлогизма):

A ® B, B ® C

A ® C

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

A ® B, A ®Ø B

Ø A

7. Правило контрапозиции:

A ® B

Ø B ®Ø A

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

( A & B )® C

(A &Ø C)®Ø B

9. Правило сечения:

A ® B, ( B & C )® D

(A & C)® D

10. Правило импортации (объединения посылок):

A ®( B ® C )

(A & B)® C

11. Правило экспортации (разъединения посылок):

( A & B )® C

  A ®(B ® C)

12. Правила дилемм:

а) A ® C, B ® C, A Ú B; б) A ® B, A ® C, Ø B ÚØ C;

            C                                 Ø A

в) A ® B, C ® D, A Ú C; г) A ® B, C ® D, Ø B ÚØ D.

          B Ú D             Ø A ÚØ C

Примеры рассуждений, не являющихся правильными:

а) A ® C, B; б) A ® B, Ø A; в) A Ú B, A и др.

    A             Ø B Ø B

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

 

Пример 1. К каким схемам относятся следующие рассуждения:

1. “Если рабочий отсутствовал на работе, он не выполнил задания. Он не выполнил задания. Следовательно, он отсутствовал на работе”.

2. “Этот человек постоянно живет в Москве или Санкт–Петербурге. Он не живет в Москве. Следовательно, он живет в Санкт–Петербурге”.

 

2. Обозначим в скобках каждое из простых высказываний первого рассуждения: “Если рабочий отсутствовал на работе (A), он не выполнил задания (B). Он не выполнил задания (B). Следовательно, он отсутствовал на работе (A)”.

Схема данного рассуждения

A ® B, B

A

относится к схеме (а) неправильных рассуждений.

2. “Этот человек постоянно живет в Москве (A) или Санкт–Петербурге (B). Он не живет в Москве (Ø A). Следовательно, он живет в Санкт–Петербурге (B)”.

Рассуждение правильное (см. правило 4,а):

A Å B, B

Ø A

Пример 2. Записать логической формулой следующее умозаключение:

“Если фирма приглашает на работу крупного специалиста в области новейшей технологии, то она считает ее привлекательной и разворачивает работы по изменению технологии производства своего традиционного продукта или начинает разработку нового продукта. Конкурирующая фирма пригласила на работу крупного специалиста в области новейшей технологии. Следовательно, она разворачивает работы по изменению технологии производства выпускаемого продукта или разработке нового продукта”.

Уточнить справедливость данного умозаключения.

 

Выделим простые высказывания и примем обозначения:

A – “Фирма приглашает на работу крупного специалиста в области новейшей технологии”.

B – “Фирма считает данную новейшую технологию привлекательной”.

C – “Разворачивает работы по изменению технологии производства своего традиционного продукта”.

D – “Фирма начинает разработку нового продукта”.

С учетом принятых обозначений умозаключение примет вид: “Если A, то B и (C или D). A. Следовательно, C или D. ”

Использую логические связки, получим окончательно:

((A ®(B &(C Ú D)))& A)®(C Ú D)

Для проверки правильности умозаключения восстановим схему рассуждения и сравним ее со схемой правила заключения 1:

A ®( B &( C Ú D )), A

C Ú D

В соответствии с этим правилом истинно заключение B &(C Ú D). Конъюнкция двух высказываний B и (C Ú D) истинна, если истинны оба высказывания. Полагая, что B истинно (что видно из контекста), истинно также (C Ú D). Таким образом, данное умозаключение верно при истинности B.

 

 

Вопросы для самопроверки и упражнения.

 

1. К каким схемам рассуждений относятся следующие рассуждения:

а) “Если рабочий отсутствовал на работе, он не выполнил задания. Он отсутствовал на работе. Следовательно, он не выполнил задания.”

б) “Идет дождь или снег. Идет дождь. Следовательно, не идет снег.”

Являются ли данные рассуждения логически правильными?

2. Записать логической формулой следующие умозаключения и уточнить их справедливость:

а) “Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастет. Следовательно, правительственные расходы возрастут.”

б) “Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно, Смит был убийцей.”

 

 

Алгебра логики.

 

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

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

Алгебра логики – алгебра, образованная множеством B ={0,1} вместе со всеми возможными операциями на нем.

Функцией алгебры логики (или логической функцией) f (,..., ) называется n–арная логическая операция на B, т.е. f: ® B. Множество всех логических функций (логических операций) обозначается , | |= , множество всех логических операций n переменных –  (n), |  (n)|= .

Любую логическую функцию f (,..., ) можно задать таблицей истинности.

Особую роль в алгебре логики играют логические функции одной и двух переменных – унарные и бинарные логические операции.

Множество всех логических функций одной переменной P ₂ (1) – унарных логических операций – представлено в таблице 1.3.1 своими

таблицами истинности, |  (n)|=4:

 и  – константы 0 и 1 соответственно.

, .

Таблица 1.3.1
x	j0	j1	j2	j3
0	0	0	1	1
1	0	1	0	1
	0	x	x	1

 

Таблица 1.3.2
№	x 1	0	0	1	1	Обозначения функции	Названия функции
	x 2	0	1	0	1
0		0	0	0	0	j0(x 1, x 2)=const 0	Константа 0
1		0	0	0	1	j1(x 1, x 2)= x 1& x 2, x 1Ù x 2	Конъюнкция, функция “и”
2		0	0	1	0	j2(x 1, x 2)= x 1® x 2, x 1® x 2	Запрет x 2, левая коимпликация
3		0	0	1	1	j3(x 1, x 2)= x 1	Повтор x 1
4		0	1	0	0	j4(x 1, x 2)= x 1 x 2, x 1 x 2	Запрет x 1, правая коимпликация
5		0	1	0	1	j5(x 1, x 2)= x 2	Повтор x 2
6		0	1	1	0	j6(x 1, x 2)= x 1Å x 2, x 1∆ x 2	Сумма по mod 2, неравнозначность
7		0	1	1	1	j7(x 1, x 2)= x 1Ú x 2	Дизъюнкция
8		1	0	0	0	j8(x 1, x 2)= x 1○ x 2, x 1¯ x 2	Функция Вебба, стрелка Пирса
9		1	0	0	1	j9(x 1, x 2)= x 1~ x 2, x 1Û x 2	Эквивалентность, равнозначность
10		1	0	1	0	j10(x 1, x 2)= x 2, Ø x 2	Отрицание x 2
11		1	0	1	1	j11(x 1, x 2)= x 1 x 2, x 1Ì x 2	Обратная (правая) импликация
12		1	1	0	0	j12(x 1, x 2)= x 1, Ø x 1	Отрицание x 1
13		1	1	0	1	j13(x 1, x 2)= x 1® x 2, x 1É x 2	Прямая (левая) импликация
14		1	1	1	0	j14(x 1, x 2)= x 1| x 2, x 1/ x 2	Функция (штрих) Шеффера
15		1	1	1	1	j15(x 1, x 2)=const 1	Константа 1

 

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

Формулы (,..., ) и (,..., ) называются эквивалентными (равнозначными), если совпадают их таблицы истинности, т.е. (,..., ) = (,..., ).

Стандартный метод установления эквивалентности двух формул:

1) для каждой формулы составляется таблица истинности;

2) полученные таблицы сравнивают по каждому набору значений переменных;

3) формулы эквивалентны (=), если на сравниваемых наборах значения функции совпадают.

Пример 1. Логическая функция трех переменных задана формулой в префиксной форме:

f (, , ) = ( (, ), (, (, )))

Представить f в инфиксной форме, если , ,  – бинарные операции:  – &,  – Å,  – Ú.

 

Инфиксная форма заданной логической функции:

f (, , )=( & )Ú ( Å()))

Пример 2. Доказать эквивалентность формулы:

¯ &

Для доказательства эквивалентности составим таблицу истинности для указанной формулы.

Таблица 1.3.3
x 1	x 2	x 1 |x 2*	x 1& x 2	x 1& x 2*	x 1	x 2	x 1Ú x 2*
0	0	1	0	1	1	1	1
0	1	1	0	1	1	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	0	0	0

 

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

Пример 3. Проверить истинность правил 1 и 2 схем логически правильных рассуждений (см. 1, 2) построением таблиц истинности.

 

Правила 1 (Modus Ponens) и 2 (Modus Tollens) представляются логическими формулами:

1. ((A ® B)& A)® B;   2. ((A ® B)&Ø B)®Ø A.

Построенные таблицы истинности этих правил подтверждают их тождественную истинность.

 

Таблица 1.3.4
A	B	(A ® B)& A	Правило 1: ((A ® B)& A)® B	Ø A	Ø B	(A ® B)&Ø B	Правило 2: ((A ® B)&Ø B)®Ø A
0	0	1	1	1	1	1	1
0	1	1	1	1	0	0	1
1	0	0	1	0	1	0	1
1	1	1	1	0	0	0	1

Вопросы для самопроверки и упражнения.

 

1. Представить префиксные формулы логических функций трех переменных f (, , ) в инфиксной форме, если  – Ú,  – &,  – Å,  – Ø, и построить соответствующие таблицы истинности:

1) (, (, ( (), )));

2) ( (, ), (, (, ())));

3) ( (), (, (, (, ())))).

2. Вычислить значения функций f (, , ) на наборах:

а) (0,1,0); б) (1,1,0);

1) ( ~ )®(( & )Ú );

2) (()& )®();

3) (( ® )& )~(() ).

3. Доказать справедливость следующих соотношений:

а) x Ú (y Ú z) (x Ú y) Ú z;       г) x ×(y Ú z) x × y Ú x × z;

б) x ×(y × z) (x × y)× z;                      д) x Ú (y × z) (x Ú y)×(x Ú z).

в) x ×()Ú y × z x Ú y × z;

4. Построением таблиц истинности подтвердить справедливость правил 4–8, 10–11 (см §1.2) логически правильных рассуждений.

 

 

Булева алгебра.

Алгебра < ;å={&,Ú,Ø}>, где  – множество всех логических функций, называется булевой алгеброй. Операции и формулы булевой алгебры называют булевыми.

Сигнатура å={&,Ú,Ø} функционально полна, т.е. позволяет выразить любые другие логические функции с помощью булевых функций &,Ú,Ø.