38. Минимальная нормальная форма, минимальное и трансверсальные покрытия в логике высказываний.

Опытный логик должен уметь опр-ть три вещи:

1)минимальную нормальную форму

2)минимальное покрытие

3)трансверсальное покрытие

Нахождение точных МНФ по известной СДНФ подробно рассматривалось в логике Буля. Если минимизировать СДНФ из 6 конституент одним из известных способов то получим МНФ: , , , ; , , D, ; B, C, D, .

Минимальное покрытие-покрытие с наименьшим числом тербов:

В нашем примере (смотри предыдущий вопрос) это заключение = ; , в входят два решающих высказывания, связанных с правдивостью кассира (А), (E).

Все остальные заключения (B, C, D) являются вторичными и могут выступать в качестве результатирующих заключений вместе с A и E.

Трансверсальное покрытие должно включать все имеющиеся тербы. В нашем примере(смотри вопрос 37)

1) ; B, C, D, - отображает наиболее полную картину

2) , ; C, D, - заключение C

3) , , ; D, -

4) , , , ,

Возьмем, для примера, : оно имеет 3 исхода истинного значения при совместном действии всех 5 факторов.

1) , , =1 и D, =0

2) , , =0 и D, =1

3) , , =1 и D, =1

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

39. Доказательство логических высказываний с помощью метода резолюций.

Этот метод является полу конструктивным методом доказательства истинности логических клауз, в которых исполняются так называемый признак резолюций. Он соответствует аксиоме отношения порядка и вместе с тем образует эффективную конструктивную структуру. Его суть сводится к тому, что 2 посылочных дизъюнкции с противоположными тербами всегда можно склеить в один дизъюнкт, в котором противоположных тербов не будет: , где х, у – произвольные тербы или дизъюнкты, А и - противоположные тербы.

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

-не обязательно использовать все посылки, число которых может быть избыточным, а главное - получить 0.

ПРИМЕР:

Док-во. начнем с приведения ее в нормальное коньюктивное противоречие:

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

Получили 0 – истинность доказана.

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

Предикат - функциональное высказывание.

Высказывание – предикатная константа.

Логика предикатов - это расширение логики высказываний за счет использования предикатов в роли логических функций. Эти функции отличаются от функций в логике Буля.

Булева функция - однородна, т.е. для нее область определения функции и область определения аргумента у нее одна и та же. Это логическая область. (0 или 1, ложь либо истина).

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

ПРИМЕР:

= «Петя читает Пушкина»

= «Рома читает Пушкина»

= «Ваня читает Пушкина»

Вместо , , можно ввести предикат , где х ={Петя, Ваня…}, а =«Х читает Пушкина»

Изменим:

= «Петя читает Пушкина»

= «Рома читает Достоевского»

= «Ваня читает Островского»

Тогда Двуместный предикат: = «Х читает У»

Введем 3-х местный предикат: P(x, y, z), который означает, что “x есть сумма y и z”

P(x, y, z)=0 (x y+z)

P(x, y, z)=1 (x=y+z)

Пусть x=5, тогда 3-х местный предикат превратится в 2-х местный.

P(5, y, z)= (y, z)=”5 есть сумма y и z”

Пусть x=5 и y=3 -одноместный

P(5, 3, z)= (z)=”5 есть сумма 3 и z”

z=2, 0-местный предикат или константа

”5 есть сумма 3 и 2”

Если бы мы приняли z=1, то P(5, 3, 1)=0, таким образом при замещении предикатом предикатной переменной величиной происходит превращение n-местного предиката в n-1-местный предикат, если принимать конкретное значение всем, то получим предикатную константу P( , ,…, ,…, )-предикатная константа, к которой применимы все лог-их высказываний.