Продолжение Лекции 2. Лекция 3

Интерполяционная теорема

Упражнение

Доказать интерполяционную теорему:

Если пропозициональная формула АВ – тавтология и формулы А и В не являются тавтологиями, то существует пропозициональная формула С, содержащая только те переменные, которые входят как в А, так и в В, такая, что формулы АС и СВ суть тавтологии.

Пояснение:

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

А – не тавтология. Следовательно, при каких-то переменных А – Л А – И. Хотя при других переменных может быть А – Л.

В - не тавтология. Следовательно, при каких-то переменных В-Л. Хотя при других переменных может быть В – И.

Итак А Л (не есть противоречие) и В И (не есть тавтология).

АВ – тавтология. Следовательно, если А – И, то В – И, или, если А – Л, то В – любое.

АС – тавтология. Следовательно, если А – И, то С – И, или, если А – Л, то С – любое.

СВ – тавтология. Следовательно, если С – И, то В – И, или, если С – Л, то В – любое.

Отсюда следует, что если АВ – тавтология, то чтобы нашлось С, что АС и СВ суть тавтологии, надо, чтобы формулы А, В, С принимали значения:

А-И, С-И, В-И;

А-Л, С- любое, В- И.

А-Л, С-Л, В-Л.

А	В	С	АВ	А	АС	СВ
*И	И	И	И	Л	И	И
И	И	Л	И	Л	Л	И
И	Л	И	Л	Л	И	Л
И	Л	Л	Л	Л	Л	И
*Л	И	И	И	И	И	И
*Л	И	Л	И	И	И	И
Л	Л	И	И	И	И	Л
*Л	Л	Л	И	И	И	И

Подходящие варианты отмечены в истинностной таблице звездочками.

Причем, только для 1-го отмеченного варианта можем утверждать, что А И, т.е. А Л,

и для 4-го отмеченного варианта можем утверждать, что В И. Таким образом, чтобы выполнить условие теоремы, формулы для А, В, С должны включать 1-й и 4-й отмеченные звездочкой * варианты, а может и другие из отмеченных вариантов. Т.е., в зависимости от значений входящих в них, т.е. в А, В, С, переменных, истинностная таблица должна давать значения А, В, С, только отмеченные звездочкой, причем 1-й и 4-й отмеченные варианты должны обязательно присутствовать!

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

Откуда возникло требование А Л, В И? Причина, на мой взгляд, следующая. Если А Л, В И, то С можно взять любое. В самом деле независимо от значений С – И или Л. АС и СВ принимает в этом случае значение И. И в этом случае теорема не интересна, т.к. С очевидно существует. Т.е., если С₁,…,С_n – переменные входящие в А и В, то в качестве С можно взять любую формулу, зависящую только от С₁,…,С_n.

Доказательство (неверное):

Если в качестве С взять А, то АС равносильно АА, что есть И (тавтология).

СВ равносильно АВ что по условию теоремы есть тоже И.

Аналогично в качестве С можно взять В. Причем нам не понадобились условия А Л и В И.

Доказательство неверно, т.к. формула С в этих случаях может содержать переменные, которые входят в А, но не входят в В или наоборот. По условию же теоремы, формула С содержит только те переменные, которые входят как в А, так и в В. Кстати, поэтому видимо теорема и называется интерполяционной. Также, видимо теорема называется интерполяционной еще и потому, что из АВ И следуетАС И и СВ И, т. е. как бы в следование из А формулы В вставили следование через формулу С.

Правильное доказательство:

При доказательстве следует учитывать следующую зависимость формул от переменных С_i, А_j, В_k:

С=С (С₁,…,С_n), А=А (С₁,…,С_n, А₁,…, А_m), В=В (С₁,…, С_n, В₁,…, В), А Л, В И.

В качестве конкретных значений переменных С_i, А_j, В_k могут подставляться конкретные высказывания, имеющие конкретные истинностные значения И или Л.

Для доказательства теоремы приведем алгоритм, строящий формулу С. Рассуждения, приведшие нас к такому алгоритму, изложены в моей тетради.

1. В качестве С возьмем С= В(С₁,…, С_n, В₁^*,…, В^*), где в качестве В₁^*,…, В^* выбираем любые высказывания, т.е. В₁^*,…, В^* могут иметь любые истинностные значения при единственном ограничении: должно быть при данном конкретном наборе С₁,…, С_n значение В(С₁,…, С_n, В₁^*,…, В^*) иметь значение Л. Следовательно и С будет иметь значение Л. Следовательно, СВ принимает значение И. Докажем, что АС принимает значение И.

Действительно АВ – И при любом выборе переменных, т.к. по условию теоремы АВ есть И (тавтология).

Отсюда следует, что, так как при заданном выборе С₁,…, С_n, есть значения переменных В₁,…, Вравные В₁^*,…, В^*, при которых В(С₁,…, С_n, В₁,…, В) – Л, то А(С₁,…,С_n, А₁,…, А_m) должно быть Л при заданном выборе С₁,…, С_n и выбранных В₁^*,…, В^*. При этом изменение А₁,…, А_m не может оказать влияние на значение формулы А. Если мы начнем менять В₁,…, В, то А(С₁,…,С_n, А₁,…, А_m) меняться не будет, т.к. формула А не зависит от В₁,…, В. Следовательно А(С₁,…,С_n, А₁,…, А_m) будет Л при любых В₁,…, В. Итак при заданном выборе С₁,…, С_n, формула А=А(С₁,…,С_n, А₁,…, А_m) будет Л при любых В₁,…, Ви А₁,…, А_m.

Итак мы получили, что при заданном выборе С₁,…, С_n, формулы А, С принимают значения Л. При этом значение В может быть любым. Следовательно, АС – И и СВ – И.

2. Если же при данном конкретном наборе С₁,…, С_n нет ни одного набора В₁,…, В, что В будет иметь значение Л, т.е. В(С₁,…, С_n, В₁,…, В) имеет значения И при любых В₁,…, В, то берем в качестве С(С₁,…, С_n) значения В(С₁,…, С_n, В₁,…, В), где В₁,…, Впринимают любые значения без ограничений. В этом случае В принимает значения И. Следовательно С – тоже И. Так как по условию теоремы АВ есть И, а, как только что установили, В – И, то следовательно А может быть и Л и И. Значит АС и СВ есть И.

Итак, мы построили С и, следовательно, доказали интерполяционную теорему.

Упражнение на дом.

Доказать, что в качестве С в интерполяционной теореме, при заданном выборе С₁,…, С_n, можно взять:

1) А(С₁,…,С_n, А₁^*,…, А_m^*), если оно имеет значение И и

2) А(С₁,…,С_n, А₁,…, А_m), если значение А – Л, при любом А₁,…, А_m. Тогда надо при выбранном С₁,…, С_n взять любое А₁,…, А_m.

Возникает вопрос является ли так заданная С формулой. Действительно, мы имеем для любых вариантов задания значений С₁,…, С_n какое-то значение выражения С(С₁,…, С_n), значение которого И или Л. Так как вариантов значений С₁,…, С_n 2ⁿ и на каждый приходится 2 возможных значения С, равных И или Л, следовательно, максимальное число функций . Причем мы не различаем между собой функции, отличающиеся видом связи переменных, если они имеют одинаковое истинностное значение (пример, Р₁Р₁ и Р₁&Р₁). Оказывается (мы докажем в дальнейшем для функции двух переменных), что все эти различных функций от переменных С₁,…, С_n можно выразить виде формул, куда входят С₁,…, С_n и логические связки. Отметим, что описанный алгоритм обязательно даст какую-то функцию С(С₁,…, С_n), может быть и не одну. Отметим также, что мы нигде не использовали требования А Л, В И. Тогда откуда возникло это требование? Причина, на мой взгляд, следующая. Если А Л, В И, то С можно взять любое, т.е. в качестве С (С₁,…, С_n) можно взять любую из функций. В самом деле независимо от значений С – И или Л. АС и СВ принимает в этом случае значение И.

И в этом случае теорема не интересна, т.к. С очевидно существует.

Практика 2

Высказывания и высказывательные формы. Истинностные таблицы.

Приведем условие простейшей задачи №5 из билета №1 первой контрольной, относящуюся к интерполяционной теореме:

Для A=C₁ÙA₁, B=B₁®C₁ (проверить, что A®B= И), найти C=С(С₁), что A®C= И, C®B= И.

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

Интерполяционная теорема

Если A®B= И, А¹ Л, В¹ И.

А=А(С₁,…,С_n, А₁,…, А_m), В=В(С₁,…, С_n, В₁,…, В), то

существует С=С(С₁,…, С_n), что формулы А®С= И, С®В= И.

Задачи будут придумываться так:

Для выбранных n, m, l буду строить таблицы истинности для A, B, удовлетворяющих условию задачи. Потом по следующему алгоритму, буду находить таблицу истинности для C. Алгоритм (в квадратных скобках красным цветом показан другой вариант алгоритма):

1) Перебираем таблицу истинности для С, A, B. Значения С еще не заполнены.

2) Находим строки в которых В(С₁,…, С_n, В₁^*,…, В^*)=Л [А(С₁,…,С_n, А₁^*,…, А_m^*)=И].

Если для С₁,…, С_n такие строки есть, то задаем для таких С₁,…, С_n

С(С₁,…, С_n)=Л [С(С₁,…, С_n)=И].

3) Для С₁,…, С_n, для которых нет ни при каких В₁,…, В[А₁,…, А_m] значений

В(С₁,…, С_n, В₁,…, В)=Л [А(С₁,…,С_n, А₁,…, А_m)=И], т.е. при любых В₁,…, В[А₁,…, А_m] для данных С₁,…, С_n В(С₁,…, С_n, В₁,…, В)=И [А(С₁,…,С_n, А₁,…, А_m)=Л], то и С(С₁,…, С_n)=И [С(С₁,…, С_n)=Л]задаем.

Я, для A, B. С, а студенты для С по таблицам истинности строят СДНФ (совершенную дизъюнктивную нормальную форму) так, как изложено в лекции 6.

Задачу формулирую так:

Для данных А, В (заданных формулами), проверить, что A®B= И. Найти С(С₁,…, С_n). Сначала таблицу истинности, а потом СДНФ, что А®С= И, С®В= И.

Итак:

1-ый вариант.

С1	А1	В1	¹Л А	¹И В	=И A®B	С	=И А®С	=И С®В
1			1 [1]	1		1[1]
1			1 [1]	1		1[1]
1			0 [0]	1		1[1]
1			0 [0]	1		1[1]
0			0 [ 0 ]	0		0 [ 0 ]
			0 [ 0 ]			0 [ 0 ]
			0 [ 0 ]			0 [ 0 ]
			0 [ 0 ]			0 [ 0 ]

СДНФ: A= С₁¹∧ A₁¹= С₁ ∧ A₁

B= (С₁¹∧ B₁¹) ∨(С₁¹∧ B₁⁰) ∨(С₁⁰∧ B₁⁰)= (С₁∧ B₁) ∨(С₁∧ B₁) ∨(С₁∧ B₁)=

=(С₁∧ (B₁ ∨ B₁) ∨(С₁∧ B₁)= (С₁ ∨(С₁∧ B₁)= (С₁∨ С₁) ∧ (С₁∨ B₁)= С₁∨ B₁= B₁®С₁.

C=С₁¹=С₁.

Итак задача: Для A=C₁ÙA₁, B=B₁®C₁ (проверить, что A®B= И), найти C=С(С₁), что A®C= И, C®B= И.

0-ой вариант.

С1	С2	А1	В1	¹Л А	¹И В	=И A®B	С	=И А®С	=И С®В
				1 [ 1 ]	1		1 [ 1 ]
				1 [1]	1		1 [ 1 ]
				1 [1]	1		1 [ 1 ]
				1 [1]	1		1 [ 1 ]
				1 [ 1 ]	1		1 [ 1 ]
				1 [1]	1		1 [ 1 ]
				0 [0]	1		1 [ 1 ]
				0 [0]	1		1 [ 1 ]
				0 [ 0 ]	0		0 [ 0 ]
				0 [ 0 ]			0 [ 0 ]
				0 [ 0 ]			0 [ 0 ]
				0 [ 0 ]			0 [ 0 ]
				0 [0]	1		1 [ 1 ]
				0 [0]	1		1 [ 1 ]
				1 [ 1 ]	1		1 [ 1 ]
				1 [1]	1		1 [ 1 ]

СДНФ: A= (С₁¹∧С₂¹∧ A₁¹) ∨(С₁¹∧С₂¹∧ A₁⁰) ∨(С₁¹∧С₂⁰∧ A₁¹) ∨(С₁⁰∧С₂⁰∧ A₁⁰) =

= (С₁∧С₂∧ A₁) ∨(С₁∧С₂∧ ØA₁) ∨(С₁∧ØС₂∧ A₁) ∨(ØС₁∧ØС₂∧ØA₁)=

= ((С₁∧С₂)∧ (A₁ ∨ ØA₁)) ∨(С₁∧ØС₂∧ A₁) ∨(ØС₁∧ØС₂∧ØA₁)=

= (С₁∧С₂) ∨(С₁∧ØС₂∧ A₁) ∨(ØС₁∧ØС₂∧ØA₁)= (С₁∧(С₂ ∨(ØС₂∧ A₁))) ∨(ØС₁∧ØС₂∧ØA₁)=

= (С₁∧((С₂ ∨ØС₂)∧(С₂ ∨A₁))) ∨(ØС₁∧ØС₂∧ØA₁)= (С₁∧(С₂ ∨A₁)) ∨(ØС₁∧ØС₂∧ØA₁)=

= (С₁∧(С₂ ∨A₁)) ∨(ØС₁∧Ø(С₂∨A₁))=С₁ «(С₂∨ A₁)

B= (С₁¹∧С₂¹∧B₁¹) ∨(С₁¹∧С₂¹∧B₁⁰) ∨(С₁¹∧С₂⁰∧B₁¹) ∨(С₁¹∧С₂⁰∧B₁⁰) ∨

∨ (С₁⁰∧С₂¹∧B₁⁰) ∨(С₁⁰∧С₂⁰∧B₁¹) ∨ (С₁⁰∧С₂⁰∧B₁⁰) =

= (С₁∧С₂∧B₁) ∨(С₁∧С₂∧ØB₁) ∨(С₁∧ØС₂∧B₁) ∨(С₁∧ØС₂∧ØB₁) ∨

∨ (ØС₁∧С₂∧ØB₁) ∨(ØС₁∧ØС₂∧B₁) ∨ (ØС₁∧ØС₂∧ØB₁) =

= (С₁∧С₂) ∨(С₁∧ØС₂) ∨ (ØС₁∧С₂∧ØB₁) ∨(ØС₁∧ØС₂) =

= С₁ ∨ (ØС₁∧((С₂∧ØB₁) ∨ØС₂) = С₁ ∨ (ØС₁∧(С₂∨ØС₂)∧(ØB₁ ∨ØС₂)) =

= С₁ ∨ (ØС₁∧(ØB₁ ∨ØС₂)) = (С₁ ∨ ØС₁)∧(С₁ ∨(ØB₁ ∨ØС₂)) = C₁ÚØC₂ÚØB₁.

C= (С₁¹∧С₂¹) ∨(С₁¹∧С₂⁰) ∨(С₁⁰∧С₂⁰) = (С₁∧С₂) ∨(С₁∧ØС₂) ∨(ØС₁∧ØС₂) =

= (С₁∧(С₂ ∨ØС₂)) ∨(ØС₁∧ØС₂) = С₁ ∨(ØС₁∧ØС₂) = (С₁ ∨ØС₁)∧ (С₁ ∨ØС₂) =

=С₁∨ØС₂.= С₂® С₁.

Итак задача: Для A= С₁ «(С₂∨ A₁), B= C₁ÚØC₂ÚØB₁ (проверить, что A®B= И), найти C=С(С₁,C₂), что A®C= И, C®B= И.

Дата добавления: 2014-01-20