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

1. Вначале помещаем помеченную формулу tK (или fК) в корень. Затем продолжаем построение по индукции.

2. Шаг n. Пусть уже построена семантическая таблица T_n.

3. Шаг n+1. Расширим семантическую таблицу Т_n до семантической таблицы Т_n+1.

   1. Из всех обычных вершин Т_n, ближайших к корню, выбираем самую левую. Обозначим выбранную вершину через X.

   2. К концу каждой непротиворечивой ветви семантической таблицы Т_n мы присоединяем атомарную семантическую таблицу, имеющую корнем X. (При этом вершина X становится особой вершиной.)

   3. В результате получаем семантическую таблицу Т_n+1.

   4. Построение заканчивается, если каждая непротиворечивая ветвь не содержит обычных вершин.

Пример. Рассмотрим закон Пирса ((А  В) А)  А. Докажем, что закон Пирса является тавтологией.

В корень таблицы поместим утверждение, что высказывание ((А  В) А)  А ложно.

f(((А  В) А)  А)

t((А  В) А)

fА

tА

fB

tA

f(А  В)





Поскольку все ветви противоречивы, получаем противоречивую семантическую таблицу, следовательно, обратная гипотеза t(((А  В) А)  А) (закон Пирса) логически истинна.

Определение. Доказательством, или выводом по Бету высказывания К называется замкнутая противоречивая семантическая таблица, в корне которой помещена помеченная формула fК.

Определение. Замкнутая противоречивая таблица, имеющая в качестве корня tK называется опровержением по Бету высказывания К.

Говорят, что высказывание К доказуемо, или выводимо по Бету, если оно имеет доказательство по Бету. Высказывание К называется опровержимым по Бету, если существует опровержение К по Бету. Тот факт, что К доказуемо по Бету, обозначается ⊢_B К.

Корректность и полнота доказательств по Бету. Справедливы теоремы о корректности и полноте доказательств по Бету. Каждая тавтология доказуема по Бету (полнота доказательств по Бету) и, наоборот, каждое доказуемое по Бету высказывание есть тавтология (корректность доказательств по Бету).

Задание 3. Доказать, используя семантические таблицы Бета, справедливость следующих законов:

(A  B) (A  B) (A  (B  C))  ((A  B)  (A  C)) (AB)  (B  A) (A(BC))  ((AB) C) (BC)((AB)(AC))

(AB)((BC)(AC)) (AB)  (A  B) (AB)  (AB)(BA) (AB)  (A  B) (AB)  (A  B)

Задание 4. Предположим, что истинны оба высказывания:

1. Джордж любит Марию, или Джордж любит Екатерину;

2. Если Джордж любит Марию, то он любит Екатерину.

Выясните методом семантических таблиц: «Кого же Джордж любит?».

Указание. Введите обозначения для высказываний «Джордж любит Марию» (M) и «Джордж любит Екатерину» (E). Запишите в виде формулы (A) конъюнкцию высказываний 1 и 2 (предполагается, что эта формула истинна, т.е. гипотеза tA - верна). Проверьте справедливость гипотез tM или fM или tE или fE с учетом истинности гипотезы tA и ответьте на поставленный вопрос: «Кого же любит Джордж?»