Свойства следования

[предыдущая глава]  [оглавление]  [следующая глава]

Теорема 8.0 Операция "" транзитивна.

Доказательство Транзитивность означает, что: если A B = true и B C = true, то A C = true. Представим условие в виде формулы РБА: (A B) & (B C)    (1) Частично раскроем сокращения: (A B) & (B C) = A & ~B & (A B) & B & ~C & (B C)     (2) Теперь раскроем сокращения в следствии теоремы: (A C) = A & ~C & (A C)    (3) Надо доказать, что формула (3) истинна. Для этого надо доказать, что в ней истинны все три множителя. Если по условию формула (2) истинна, то истинны все 6 множителей, которые в ней есть. Среди них есть есть множители A и ~C, истинность которых нам надо было доказать. Таким образом, нам остается доказать, что и последний множитель: (A C) = true. Рассмотрим часть формулы (2): (A B) & (B C). Эти множители истинны, как и все остальные шесть. Таким образом, (A B) & (B C) = true. Но по теореме 04.3 (A B) & (B C) = ((A B) & (B C)) Следовательно ((A B) & (B C)) = true    (4) Рассмотрим формулу: ((A B) & (B C)) (A C) Она истинна при любых A, B, C, что проще всего доказать, составив таблицу истинности. То есть: (((A B) & (B C)) (A C)) = true    (5) Из формул (4) и (5) и теоремы 04.4 следует, что (A C) = true И это был последний множитель в формуле (2), истинность которого надо было доказать.

Теорема 8.1 (A B) = (~B ~A)

Доказательство Начинаем с формулы, по которой вычисляется истинность правой части, и приходим к формуле, по которой получается истинность левой части: ~B ~A = ~B & ~~A & ~ (~B & ~~A) = ~B & A & ~ (~B & A) = A & ~B & ~ (A & ~B) = A B

Теорема 8.2 Пусть A B истинно. x - свободная переменная в формулах A и B (или одной из них). F - формула. F не содержит свободных переменных, одноименных со свободными переменными формул A и B. Множество значений формулы F совпадает с областью значений переменной x. AF - формула, полученная подстановкой формулы F в формулу A на место каждого вхождения переменной x (если она есть в формуле A). BF - формула, полученная подстановкой формулы F в формулу B на место каждого вхождения переменной x (если она есть в формуле B). Свободные переменные из F остаются свободными после подстановки. - тогда: AF BF

Доказательство Краткое пояснение по поводу пункта 8. Некоторые фрагменты формул могут сделать из свободных переменных связанные. Например, в формуле x (x + y = 10)    (1) - переменная y свободная. В формуле z / x    (2) - две свободных переменных: x и z. Однако если подставить формулу (2) на место переменной y в формуле (1), то получится формула, в которой ранее свободная (в формуле (2)) переменная x окажется связанной, благодаря квантору: x (x + z/x = 10) Условие теоремы запрещает подобные подстановки. Список свободных переменных в формулах AF и BF , не совпадает со списком свободных переменных в A и B. Но, благодаря пунктам 4 и 8, мы точно знаем, какие свободных переменные в них будут. Там будут все свободные переменные из формул A и B, кроме переменной x, и дополнительно все свободные переменные формулы F. Поскольку истинно общее следование в пункте 1, то истинна формула A.    (3) Пусть для определенности в формуле A есть свободные переменные x, a1,...an. Тогда можно выбрать какую-нибудь комбинацию значений переменных x', a'1,...a'n, при которой A = true. Нам надо доказать, что истинно AF.    (4) Возьмем комбинацию x', a'1,...a'n и уберем из нее значение x', соответствующее параметру x, однако запомним его. Получим комбинацию a'1,...a'n Пусть для определенности в формуле F есть свободные переменные f1,...fm. Благодаря пункту 5, для любого значения параметра x можно подобрать комбинацию значений переменных формулы F, при которой она будет равна этому значению. Возьмем конкретное значение x' и найдем какую-нибудь комбинацию значений f'1,...f'm, при которой F = x'. Теперь возьмем комбинацию значений a'1,...,a'n, f'1,...f'm. Это возможно, так как в А и в F нет одинаковых переменных (благодаря пункту 4). Для этой комбинации AF = true. В самом деле: значения f'1,...f'm будут подставлены в те части формулы AF, где была подставлена формула F, но они не попадут в другие части формулы (благодаря пункту 4). На значение остальных частей формулы будут влиять переменные a'1,...,a'n, которые, опять же, не попадут в те части формулы, которые возникли в результате подстановки. Специальный подбор комбинации обеспечит, чтобы вычисление формулы F при вычислении формулы AF дало тот же самый результат x', что и простая подстановка x' вместо x. Наконец, пункт 8 даст гарантию, что внешние (по отношению к подставленным) части формулы не повлияют на вычисление F. Кстати, можно сформулировать этот пункт и таким образом (что нет влияния и т.д.) Таким образом, подходящая комбинация значений найдена, и формула (4) доказана. Аналогично на основе формулы: ~B. доказывается формула: ~BF.    (5) Для доказательства следования AF BF необходимо доказать: AF & ~BF & (AF BF) Первые два множителя конъюнкции уже доказаны - это формулы (4) и (5). Остался последний множитель, который здесь выражен через материальную импликацию. Нам уже дано по условию, что (A B) Квантор всеобщности означает, что формула под квантором - общезначимая. Но подстановка формул на место свободной переменной в общезначимую формулу не нарушает ее общезначимости при соблюдении некоторых минимальных требований. Что касается "минимальных требований", то первое из них указано в пункте 8, а второе является смягченным вариантом пункта 5: множество значений F должно быть подмножеством (собственным или несобственным) области определения параметра x. Поскольку по условию верен пункт 5, то это требование тем более соблюдается. Доказательство этого правила в разной форме есть, например, у С.Клини (S.C.Kleene, Mathematical Logic, 1967, с. 24-25б 120-124). Если пересказать его вкратце, то при вычислении AF придется сначала вычислить подставленные F, получится результат в пределах области определения переменной x, а дальше процесс вычисления будет совпадать с вычислением A с учетом ранее вычисленного x. То же самое и для BF. В результате истинность AF и BF для произвольно взятого v окажется той же самой, что и истинность A и B для какой-то комбинации значений переменных. А для любой комбинации под квантором получится true.

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

1. В этих столбцах есть хотя бы одна комбинация true, true.
2. В этих столбцах есть хотя бы одна комбинация false, false.
3. В этих столбцах нет ни одной комбинации true, false.

Если все три требования соблюдаются, результат операции общего следования - true, иначе - false. Рассмотрим самые важные примеры истинных общих следований:

x & y x		x & y y		x x y		y x y
Таблица истинности:		Таблица истинности:		Таблица истинности:		Таблица истинности:
x y x & y x false false false false false true false false true false false true true true true true		x y x & y y false false false false false true false true true false false false true true true true		x y x x y false false false false false true false true true false true true true true true true		x y y x y false false false false false true true true true false false true true true true true

x x		x & (x y) ~y		~x & (x y) y
Таблица истинности:		Таблица истинности:		Таблица истинности:
x x x false false false true true true		x y x & (x y) ~y false false false true false true false false true false true true true true false false		x y ~x & (x y) y false false false false false true true true true false false false true true false true