Построение полных таблиц истинности и их использование в КЛВ

Алгоритм построения полной таблицы истинности

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

Опишем алгоритм построения такой полной таблицы, называемой таблицей истинности для данного высказывания. В качестве примера возьмем такое сложное высказывание:

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

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

«Смит был убийцей» — «Джонс лжет» — q, «Браун встречал Смита этой ночыо» — s. Тогда логическая форма всего сложного высказывания будет такой: 1 р з (q & 1 s).

Далее подсчитывают число строк в будущей таблице. Это делается по формуле

где N — искомое число строк, т — число возможных значений аргументов, а п — число этих аргументов (т.е. различных переменных в формуле).

В частности, для КЛВ эта формула выглядит так:

Нетрудно понять, почему формула именно такова. В теории вероятности с помощью такой формулы подсчитывают с точностью до порядка элементов число различных выборок этих элементов длиной п, если всего существует т различных типов таких элементов[1]. Два — это количество возможных значений аргументов в КЛВ — «истина» и «ложь». В трехзначной логике Лукасевича (где кроме «истины» и «лжи» вводится истинностная оценка «неопределенно») основанием степени будет 3. И для трех переменных в таблице будет уже не 8 (как в КЛВ), а 27 строк.

Строим таблицу, предварительно выписывая все различные переменные, входящие в формулу:

р

<7

S

и

И

и

и

И

л

и

л

и

и

л

л

л

и

и

л

и

л

л

л

и

л

л

л

Заполненная часть называется входами таблицы. Фактически это систематическое перечисление всех возможных комбинаций значений трех аргументов. При этом пользуются следующим правилом, позволяющим эффективно перечислить все такие комбинации (т.е. и ни разу не повториться, и ни одну не пропустить). В крайнем столбце входов (здесь в качестве такового выбран крайний правый) «истина» и «ложь» чередуются «но одной», в следующем (здесь он центральный) — но две, в следующем (здесь он последний, крайний левый) — по четыре. Если бы переменных было 4, то строчек было бы тогда 16, а чередование было бы, например, таким (слева направо): по восемь — по четыре — по две — по одной. В трехзначной логике Лукасевича в таблице для трех переменных чередование было бы таким: по девять (9 раз «истина», 9 раз «ложь», 9 раз «неопределенность»), по три, по одной.

Далее в ту же строку, в которой записаны сами переменные, пишем нашу формулу и расставляем «порядок действий»:

1

4

3

2

р

я

.9

1

V

=>

&

1

S)

и

и

и

и

и

л

и

л

и

и

л

л

л

и

и

л

и

л

л

л

и

л

л

л

А теперь начинаем заполнять таблицу, рассчитывая значение всей формулы для каждого из 8 возможных случаев. Но в целях удобства и быстроты работы таблица строится не по строчкам (сначала вычислить значение формулы в 1-й строчке, затем во 2-й и т.д.), а по столбцам («действиям»):

1

4

3

2

р

я

5

1

=>

(<7

&

1

•*)

и

и

и

л

л

и

и

л

л

и

и

л

и

л

л

и

л

л

л

и

л

и

и

и

л

л

и

л

и

и

л

л

и

и

л

л

л

л

и

и

Теперь перенесем значения q из входов таблицы в соответствующий столбец в правой части и посчитаем значение конъюнкции q & ls> выступающей в роли консеквента всей исходной формулы-импликации:

1

4

3

2

р

<7

5

1

3

&

1

S)

и

и

и

л

и

л

л

и

и

л

л

и

и

и

и

л

и

л

л

л

л

и

л

л

л

л

л

и

л

и

и

и

и

л

л

л

и

л

и

и

и

и

л

л

и

и

л

л

л

л

л

л

и

л

л

и

При определении значений формул типа А®В (где ® — некоторая двухместная связка), в процессе построения таблиц истинности пользуются следующими эвристико-мнемоническими приемами.

  • 1. Если ® — это конъюнкция, то ищем строки, в которых оба аргумента истинны, и там пишем в качестве значения всей «обсчитываемой подформулы» «истина», а во всех остальных строчках пишем не глядя «ложь».
  • 2. Если ® — это дизъюнкция, то ищем строки, в которых оба аргумента ложны, и там пишем в качестве значения всей «обсчитываемой подформулы» «ложь», а во всех остальных строчках пишем не глядя «истина».
  • 3. Если ® — это импликация, то ищем строки, в которых слева (т.е. в качестве значения антецедента) стоит «истина», а справа (в качестве значения консеквента) «ложь», и там пишем в качестве значения всей «обсчитываемой подформулы» «ложь», а во всех остальных строчках пишем не глядя «истина».
  • 4. Если ® — это эквиваленция, то ищем строки, в которых оба аргумента принимают одинаковое значение, и там пишем в качестве значения всей «обсчитываемой подформулы» «истина», а во всех остальных строчках пишем не глядя «ложь».
  • 5. Если ® — это строгая дизъюнкция, то ищем строки, в которых оба аргумента принимают разное значение, и там пишем в качестве значения всей «обсчитываемой подформулы» «истина», а во всех остальных строчках пишем не глядя «ложь».
  • 6. Если А и В — либо пропозициональные переменные, либо их отрицания, то полезно помнить, что соответствующая конъюнкция истинна всегда ровно в четверти возможных случаев (1 из 4, 2 из 8, 4 из 16 и т.д.), строгая дизъюнкция и эквиваленция — в половине случаев (2 из 4, 4 из 8, 8 из 16 и т.д.), дизъюнкция и импликация — в трех четвертях случаев (3 из 4, 6 из 8, 12 из 16 и т.д.). Подчеркиваем — это имеет место в обязательном порядке только для таких формул вида А®В, в которых А и В — либо пропозициональные переменные, либо их отрицания!

Завершим работу над таблицей («отслужившие свое» столбики стерты):

1

4

3

2

р

я

S

1

р

D

(

&

1

S)

и

и

и

л

и

л

и

и

л

л

и

и

и

л

и

л

и

л

и

л

л

л

и

л

л

и

и

и

л

л

л

и

л

и

и

и

л

л

и

и

л

л

л

л

л

и

л

л

Дальнейшая работа с таблицей зависит от того, какие задачи и вопросы ставились изначально. Например, нас могли спросить: «Каковы условия истинности этой сложной формулы 1 р z> (q & 1 s)?» Теперь мы можем и должны ответить так: «Любой из пяти следующих наборов значений переменных: ИИИ, ИИЛ, ИЛИ, ИЛЛ, ЛИЛ» (потому что при этих и только при этих наборах значений вся формула принимает значение «истина»). Соответственно, и для условий ложности (три остальных набора). Если речь идет не о формуле, а о самом высказывании, нам надо проинтерпретировать эти наборы, например (для набора ИЛИ): «Смит был убийцей, Джонс не лгал, а Браун повстречал Смита этой ночыо». Или для набора ЛИЛ: «Смит не был убийцей, Джонс лгал, а Браун не встречал Смита этой ночью».

Возможна такая ситуация. Пусть нам известно, что Смит не был убийцей. С какой логической вероятностью все исходное высказывание истинно? Находим строки, в которых переменной р приписано значение «ложь». Их четыре (с 5-й по 8-ю). Смотрим, в скольких из этих строк вся формула истинна. В одной (6-й). Стало быть, искомая вероятность — 1/4. А если нам известно, что Джонс лгал (1—2-я и 5—6-я строки), то эта вероятность составит уже 3/4.

Задача может быть и обратной. Известно, что все высказывание в целом истинно. С какой логической вероятностью Смит был убийцей? Ответ — 4/5, или 80% (в 4 из 5 строк, в которых вся формула истинна — 1—4 и 6, — переменная р имеет значение «истина»). Пусть известно, что все высказывание ложно. С какой вероятностью Смит не был убийцей? — С вероятностью 100%, так как во всех трех соответствующих строках (5-й, 7-й и 8-й) переменная р имеет значение «ложь».

  • [1] Предположим, у нас есть два типа деталей — кубики и пирамидки. Очевидно, что существует ровно восемь различных комбинаций из трех деталей — кубик-кубик-кубик, кубик-пирамидка-кубик, пирамидка-кубик-пирамидка и т.д.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >