A®B; B®C; C 3 страница

Схему дедуктивного вывода записывают так:

F ₁; F ₂;... F _n |¾ B,

где символ |¾ означает “верно, что B выводима из F ₁; F ₂;... F _n“.

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

Этот факт записывают так:

|¾ F ₁& F ₂&... & F _n®B.

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

F ₁; F ₂;... F _n

B,

где над чертой записывают множество посылок и аксиом F ₁; F ₂;...F_n, а под чертой заключение В, принимающее значение “истины” при истинности всех посылок.

 

1.2.3.1 Правила подстановки

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

Этот факт записывают так:

_Аò^ВF(А)

F(В).

 

Если F (A)= A, то _Аò^ВА

В.

 

Если F (ùA), то _Аò^ВF(ù;А)

F(ù;В).

Следует еще раз обратить внимание, что формула F должна быть выводимой в исчислении высказываний.

Пример: Пусть даны формулы F=A&C®A и B=C®ùA.

Если выполнить подстановку формулы B в формулу F вместо формулы A, то получим новую формулу F`.

_А ò ^C®ùA (A&C®A)

(C®ùA)&C®(C®ùA).

 

Проверим значения двух формул F и F’по таблицам истинности. Выделенные столбцы показывают тождество двух формул.   A	B	C	1&3	4®1	3®ù1	6&3	7®6
л	л	л	л	и	и	л	и
л	л	и	л	и	и	и	и
л	и	л	л	и	и	л	и
л	и	и	л	и	и	и	и
и	л	л	л	и	и	л	и
и	л	и	и	и	л	л	и
и	и	л	л	и	и	л	и
и	и	и	и	и	л	л	и

 

1.2.3.2. Правила введения и удаления логических связок

При выводе заключения удобно правила введения и удаления логических связок представить также как и правила вывода:

1) если посылки F ₁ и F ₂ имеют значение “и”, то истинной является их конъюнкция, т.е.

F ₁; F ₂

(F ₁& F ₂).

Эта запись при истинности посылок F ₁ и F ₂ предусматривает возможность введения в заключение логической связки конъюнкции; это правило тождественно аксиоме А5;

2) если (F ₁& F ₂) имеет значение “и”, то истинными являются подформулы F ₁ и F ₂, т.е. (F ₁& F ₂) (F ₁& F ₂)

F и F ₂.

Эта запись при истинности (F ₁&F₂) предусматривает возможность удаления в заключении логической связки конъюнкции и рассматривать истинные значения подформул F₁ и F ₂; это правило тождественно аксиомам А3 и А4;

 

3) если F ₁ имеет значение “и”, а (F ₁& F ₂) – “л”, то ложной является подформулы F ₂, т.е.

F ₁;ù(F ₁& F ₂)

ù F ₂.

Эта запись при ложности (F ₁& F ₂) и истинности одной из подформул предусматривает возможность удаления в заключении логической связки конъюнкции и рассматривать ложным значение второй подформулы;

4) если истинна хотя бы одна посылка F ₁ или F ₂, то истинной является их дизъюнкция, т.е.

F ₁ F ₂

(F ₁ ÚF ₂) или (F ₁ Ú;F₂).

Эта запись при истинности хотя бы одной подформулы F ₁ или F ₂ предусматривает возможность введения в заключение логической связки дизъюнкции; это правило тождественно аксиомам А6 и А7;

5) если (F ₁ ÚF ₂) имеет значение “и” и одна из подформул F ₁ или F ₂ имеет значение “л”, то истинной является вторая подформулаы F ₂ или F₁, т.е.

(F ₁ ÚF ₂); ù F ₁ (F ₁ ÚF ₂);ù F ₂

F ₂ или F ₁.

Эта запись при истинности (F ₁ Ú;F₂) предусматривает возможность удаления в заключении логической связки дизъюнкции и рассматривать истинные значения подформул F ₁ или F ₂;

6) если подформула F ₂ имеет значение “и”, то истинной является формула (F ₁® F ₂) при любом значении подформулы F ₁, т.е

F ₂

(F ₁® F ₂).

Эта запись при истинном значении F ₂ предусматривает возможность введения в заключение логической связки импликации при любом значении подформулы F ₁ (“истина из чего угодно”); это правило тождественно аксиоме 1;

7) если подформула F ₁ имеет значение “л”, то истинной является формула (F ₁® F ₂) при любом значении подформулы F ₂, т.е

ù F ₁

(F ₁® F ₂).

Эта запись при ложном значении F ₁ предусматривает возможность введения в заключение логической связки импликации при любом значении подформулы F ₂ (“ из ложного что угодно”);

8) если формула (F ₁® F ₂) имеет значение “и”, то истинной является формула (ù F ₂®ù F ₁), т.е

(F ₁® F ₂)

(ù F ₂®ù F ₁).

Эта запись при истинном значении (F ₁® F ₂) определяет возможность замены местами полюсов импликации при одновременном изменении их значений; это- закон контрапозиции;

9) если формула (F ₁® F ₂) имеет значение “и”, то истинной является формула ((F ₁ ÚF ₃)®(F ₂ ÚF ₃)) при любом значении F ₃, т.е

(F ₁® F ₂)

((F ₁ ÚF ₃)®(F ₂ ÚF ₃)).

Эта запись при истинном значении (F ₁® F ₂) определяет возможность выполнить операцию дизъюнкции при любом значении формулы F ₃ над каждым полюсом импликации; это правило тождественно аксиоме А11.

10) если формула (F ₁® F ₂) имеет значение “и”, то истинной является формула ((F ₁& F ₃)®(F ₂& F ₃)) при любом значении F ₃, т.е

(F ₁® F ₂)

((F ₁& F ₃)®(F ₂& F ₃)).

Эта запись при истинном значении (F ₁® F ₂) определяет возможность выполнить операцию конъюнкции при любом значении формулы F ₃ над каждым полюсом импликации; это правило тождественно аксиоме А10.

11) если формулы (F ₁® F ₂) и (F ₂®F₃) имеют значение “и”, то истинной является формула (F ₁®F₃), т.е

(F ₁® F ₂); (F ₂® F ₃)

(F ₁® F ₃).

Эта запись при истинном значении (F ₁® F ₂) и (F ₂® F ₃) предусматривает возможность формирования импликации (F ₁® F ₃) (закон силлогизма);

это правило тождественно аксиоме А2;

12) если формулы F ₁ и (F ₁® F ₂) имеют значение “и”, то истинной является формула F ₂, т.е

F ₁; (F ₁® F ₂)

F ₂.

Эта запись при истинном значении посылки F ₁ и импликации (F ₁® F ₂) позволяет удалить логическую связку импликации и определить истинное значение заключения F ₂;

13) если формулы ù F ₂ и (F ₁® F ₂) имеют значение “и”, то истинной является формула ù F ₁, т.е

ù F ₂; (F ₁® F ₂)

ù F ₁.

Эта запись при истинном значении посылки ù F ₂ и импликации (F ₁® F ₂) позволяет удалить логическую связку импликации и определить истинное значение заключения ù F ₁;

14) если формулы (F ₁® F ₂) и (F ₂® F ₁) имеют значение “и”, то истинной является формула (F ₁«F ₂), т.е

(F ₁® F ₂); (F ₂® F ₁)

(F ₁«F ₂).

Эта запись при истинном значении (F ₁® F ₂) и (F₂® F ₁) позволяет ввести логическую связку эквиваленции и определить значение формулы (F ₁«F ₂);

15) если формула (F ₁«F ₂) имеет значение “и”, то истинными являются формулы (F ₁® F ₂) и (F ₂® F ₁), т.е

(F ₁«F ₂) (F ₁«F ₂)

(F ₁® F ₂) и (F ₂® F ₁).

Эта запись при истинном значении (F ₁«F ₂) позволяет удалить логическую связку эквиваленции и определить истинное значение формул (F ₁® F ₂) и (F ₂® F ₁).

 

1.2.3.3 Правила заключения

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

а) если F _i и (F _i ® F _j) есть выводимые формулы, то F _j также выводимая формула, т.е.

F _i; (F _i® F _j)

F _j.

это правило называют modus ponens (m.p.).

b) если формулы ù F _j и (F _i® F _j) есть выводимые формулы, то ù F _i также выводимая формула, т.е

ù F _j; (F _i® F _j)

ù F _i.

это правило называют modus tollens (m.t.).

Пример: Суждение: “Сумма внутренних углов многоугольника равна 180^о (А). Если сумма внутренних углов многоугольника равна 180^о (A), то многоугольник есть треугольник (В). Следовательно, дан треугольник”.

А;A®B

B.

Пример: Суждение: ”Дан не треугольник (ùB); если сумма внутренних углов многоугольника равна 180^о(А), то многоугольник есть треугольник (В). Следовательно, сумма внутренних углов многоугольника не равна 180^о(ùA)”.

ùB; A®B

ùA.

 

1.3. Метод дедуктивного вывода

Как уже отмечалось, теорема F₁; F₂;...F_n|¾В равносильна доказательству |¾(F₁&F₂&...&F_n®B). Если каждая F_i=и, то F₁& F₂&...&F_n)=и, а если (F₁&F₂&...&F_n®B)=и, то В=и.

Следовательно, при истинности всех посылок и истинности импликации (см. правило m.p.), заключение всегда будет истинным.

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

1) |¾(F₁&F₂&...&F_n®B);

2) |¾(ù(F₁&F₂&...&F_n )ÚB);

3) |¾(ùF₁ÚùF₂ Ú...ÚùF_nÚB);

4) |¾(ùF₁ÚùF₂ Ú...ÚùF_n-1Ú(F_n®B));

5) |¾(ùF₁ÚùF₂ Ú...Ú(F_n-1®(F_n®B)));

6) |¾(ùF₁Ú(F₂ ®...®(F_n-1®(F_n®B))...));

7) |¾(F₁®(F₂ ®...®(F_n-1®(F_n®B))...)

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

Пример. Дано cуждение: “Всякое общественно опасное деяние (А) наказуемо (В). Преступление (С) есть общественно опасное деяние (А). Дача взятки (D) - преступление (C). Следовательно, дача взятки наказуема?”[6].

A®B;С®А; D®C

D®B.

1) F₁=A®B посылка;

2) F₂=С®А посылка;

3) F₃=D®C посылка;

4) F₄=C®B заключение по формулам F₁ и F₂ и

аксиоме А2 или правилу 11);

5) F₅=D®B заключение по формулам F₃ и F₄ и аксиоме

А2 или правилу 11).

Следовательно, дача взятки (D) наказуема (B).

 

Пример: “Если Петров не трус (A), то он поступит в соответ­ствие с собственными убеждениями (B). Если Петров честен (C), то он не трус (A). Если Петров не честен ù(C), то он не признает своей ошибки (D). Но Петров признает свои ошибки ù(D). Следовательно, он поступит согласно собственным убеждениям (B)?"[1]

A®B; C®A; ùC®D; ùD

B.

1) F₁=A®B посылка;

2) F₂=C®A посылка;

3) F₃=ùC®D посылка;

4) F₄=ùD посылка;

5) F₅=C®B заключение по формулам F₁, F₂ и аксиоме А2 или правилу 11);

6) F₆=ùB®ùC заключению по формуле F₅ и правилу 8);

7) F₇=ùB®D заключение по формулам F₃ и F₆ и аксиоме А2 или правилу 11);

8) F₈=B заключение по формулам F₄, F₇ и правилу m.t..

Так доказано, что Петров поступает согласно собственным убеждениям.

 

Пример: “Если команда А выигрывает в футболе то город А’ торжествует, а если выигрывает команда В, то торжествовать будет город В’. Выигрывают или А или В. Однако, если выигрывают А, то город В’ не торжествует, а если выигрывают В, то не будет торжествовать город А’. Следовательно, город В’ будет торжествовать тогда и только тогда, когда не будет торжествовать город А’”[1]

 

(A®A’)&(B®B’); (AÚB); (A®ùB’)&(B®ùA’)

(B’«ùA’).

 

1) F₁=(A®A’)&(B®B’) - посылка;

2) F₂=(A®A’) - заключение по формуле F₁ и правилу удаления логической связки конъюнкции;

3) F₃=(B®B’) - заключение по формуле F₁ и правилу удаления логической связки конъюнкции;

4) F₄=(A®ùB’)&(B®ùA’) - посылка;

5) F₅=(A®ùB’) - заключение по формуле F₄ и правилу удаления логической связки конъюнкции;

6) F₆=(B®ùA’) - заключение по формуле F₄ и правилу удаления логической связки конъюнкции;

7) F₇=(B’®ùA) - заключение по формуле F₅ и закону контрапозиции;

8) F₈=(A’®ùB) - заключение по формуле F₆ и закону контрапозиции;

9) F₉=(AÚB) - посылка;

10) F₁₀=ùA®B - заключение по формуле F₉ и правилу эквивалентного преобразования;

11) F₁₁=ùA®ùA’ - заключение по формулам F₆, F₁₀ и закону силлогизма;

12) F₁₂= B’®ùA’ - заключение по формулам F₇, F₁₁ и закону силлогизма;

13) F₁₃= ùA’®ùA - заключение по формуле F₂ и закону контрапозиции;

14) F₁₄=ùA’®B - заключение по формулам F₁₀, F₁₃ и закону силлогизма;

15) F₁₅=ùA’®B’ - заключение по формулам F₃, F₁₄ и закону силлогизма;

16) F₁₆= (B’®ùA’)(ùA’®B’)=(B’«ùA’) – заключение по формулам F₁₂, F₁₅ и правилу введения логической связки конъюнкции.

Так доказана истинность формулы (B’«ùA’).

Пример. "Если Петров говорит неправду (A), то он заблуждается (В) или сознательно вводит в заблуждение других (С). Петров говорит неправду и явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других" [2]

А®(ВÚС); A&ùB

С.

1) F₁=А®(ВÚС) - посылка;

2) F₂=A&ùB - посылка;

3) F₃=A - заключение по формуле F₂ и правилу 2);

4) F₄=ùB - заключение по формуле F₂ и правилу 2);

5) F₅=(ВÚС) - заключение по формулам F_1, F₃ и правилу m. p.;

6) F₆=C - заключение по формулам F_4, F₅ и правилу 5).

Так доказано, что Петров сознательно вводит в заблуждение других.

 

Пример: Доказать истинность заключения
А;В;(А&С ® ù В)

ù C.

1) F₁=A & C ® ù B - посылка;

2) F₂=B - посылка;

3) F₃=ù (A & C) - заключение по формулам F₁, F₂ и правилу m. t.;

4) F₄= A - посылка;

5) F₅=ù C - заключение по формула F₃, F₄ и правилу 2).

Процесс дедуктивного вывода удобно проследить на графе, вершинами которого являются формулы, а дугами – отношения между ними (см. рис.1).

 

 

Рис.1. Граф вывода заключения

Пример. Доказать истинность заключения

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

(CÚD).

1) F₁=(A®C) посылка;

4) F₂=(AÚB)®(CÚB) заключение по формуле F₁ и правилу 9);

3) F₃=(B®D) посылка;

4) F₄=(CÚB)®(CÚD) заключение по формуле F₃ и правилу 9);

5) F₅=(AÚB)®(CÚD) заключение по формулам F₂ и F₄ и правилу 11);

6) F₆=(AÚВ) посылка;

7) F₇=(CÚD) заключение по формулам F₅ и F₆ и правилу m. p..

Так доказана истинность заключения (CÚD).

 

 

Рис. 2. Граф вывода заключения

Пример: Доказать истинность заключения

 

(A®B)&(C®D); (D&B®E); ù E

ùC ÚùA.

1) F₁=(D&B®E) посылка;

2) F₂=ùE посылка;

3) F₃=ù(D&B) заключение по формулам F₁ и F₂ и правилу m. t.;

4) F₄=(А®В)&(С®D) посылка;

5) F₅=(A®В) заключение по формуле F₄ и правилу 2);

6) F₆=(С®D) заключение по формуле F₄ и правилу 2);

7) F₇=(ùB®ùA) заключение по формуле F₅ и правилу 8);

8) F₈=(ùDÚùB) заключение по формуле F₃ и закону де Моргана;

9) F₉=(D®ùB) заключение по формуле 8) и правилу введения ипликации;

10) F₁₀=(D®ù A) заключение по формулам F₇ и F₉ и правилу 11);

11) F₁₁=(С®ù A) заключение по формулам F₆ и F₁₀ и правилу 11);

12) F₁₂=(ùСÚù A) заключение по формуле F_II и правилу введения дизъюнкции.

		Рис.3. Граф вывода заключения

 

 

 

Пример: Доказать истинность заключения:

((A Ú B)® С); (С®(D Ú M)); (M®N); ((ù D)&(ù N))

ù A.

1) F₁=((ù D)&(ù N)) посылка;