Алгоритм логического вывода с применением правила резолюций

1.исключение тавтологий

S’=c S’¹ c

S выполнимо 2.однолитерный дизъюнкт L

исключение L&(LÚS)

S’=c S’¹ c

S выполнимо 3.правило резолюций

С=c S’¹ c

S невыполнимо

Правило резолюций заменяет (эквивалентно):

1) вычеркиванию контрарной литеры по правилу однолитерных дизъюнктов L&(ùLÚC)®C;

2) правило расщепления

(LÚA)&(ùLÚB)=>AÚB

Пример:

AÚB 1) AÚB

A®C 2) A®C

B®D 3)B®D

ù(CÚD) 4)ùC&ùD

Граф опровержения:

A ÚB ù A ÚCùBÚD ùCùD

BÚC ùA ùB

A

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

Дизъюнкт С называется поддизъюнктом (CÍD), если множество литер С является подмножеством множества литер дизъюнкта D.

S_­C­ÍS_­D­ D – наддизъюнкт.

Все наддизъюнкты вычеркиваются.

aÚbÍaÚbÚc - по правилу поглощения

Последовательное применение правила резолюции методом насыщения уровня.

Пример:

S₀ 1) A v B

2) ù A v C

3) ù B v D

4) ù C

5) ù D

Перебираются все возможные резольвенты

1) B v C (1,2)

2) A v D (1,3) S_­1

3) ù A (2,4)

4) ù B (3,5)

вычеркиваются наддизьюнкты

1) A v B ù C

2) ù C ù D

3) ù D ù A

4) B v C ù B ù c,c

5) B v D S2 A Þ ð

6) ù A B опровержение

7) ù B C

8) A D

9) B

10) C

11) D

ГЛАВА 2. Логика предикат

Пусть задано множество D,конечное или бесконечное.

Определение: Терм (t):

1) есть предметная константа из D (пример: aÎD)

2) переменная х, принимающая значение из D

3) функция f(t₁,..., t_n), где t_i – терма.

Пример:

D – множество целых чисел, к примеру а~3 – терм, а для х f(3),f(f(5), f(x,y)

Терм – переменная или функция и т.д.

Определение: утверждение P(t₁,..., t_n), зависящее от термов t₁,..., t_n, истинности которого зависит от значения термов называется предикатом.

Предиката – утверждение (высказывание)

Пример: Р(5) = (5 – положительное целое) – простое высказывание, оно «И», «true». (где Р – символ предикат)

R(Петров) = (Петров - студент) ~ оно «И» или «Л». (где R – предикатный символ, (Петров) - предиката)

Р(х) = (х≠5)~«И» или «Л» - в зависимости от значения х.

- с переменной или константой

Р(3) = (3≠5)~«true» - истинное простое высказывание

Р(f(х),у,4) = (e^x+y<4) (где е^х – функция, у – переменная, 4 - const)

Представляя числа из области интерпретации, например N – множество натуральных чисел.

N(e³+2<4) = P(f(3)2,4) = F ® false – ложное утверждение

Если предикат зависит от переменных, то он является истинной функцией P(x₁,...,x_n), которая принимает значение «И» или «Л», когда аргументы принимают некоторые значения из области D.

х₁,х₂,..., х_nÎD (но не обязательно) область значений D называют предметной областью, областью определения и областью интерпретации.

Предикат приобретает смысл, если для него выбрана интерпретация, т.е.

1) выбрана область интерпретации для переменных х₁, х₂,..., х_nÎD

2) выбрано свойство или отношение вместо предикатного символа:

Р(х₁,,х₂)=(х₁<х₂)

В каждой интерпретации для конкретного набора значений переменных будет получено простое высказывание, истинное или ложное по смыслу

Истинное - если удовлетворяет свойству и ложное – если нет.

Если одна переменная в предикате:

Р(х) – 1 – местный предикат

Р(х,у) – 2 – местный предикат

......

Р(x₁,..., x_n) – n – местный предикат

Если все переменные заменены предикатными константами, то тогда предикат становится высказыванием, что называют 0 – местным предикатом

Т.о. логика предикат – это обобщение логики высказывании.

2.1 Одноместные предикаты, определение события

Обозначается Р(х), но х – имеет двузначную область определения {высокий, низкий}

хÎ{H,L}

хÎ{включено, выключено}

хÎ{если, нет} и т.п.

Пример:

х – контакт

Р(х) - состояние контакта

Р(х) = {х замкнут} – утверждение (его истинность от х)

Электронная схема:

интерпретирует этот предикат

Р(х) = {х - замкнут} – True

P(x) = {х - разомкнут} – False

Р(х) = {х - сигнал} _Ç_ - есть сигнал; ----- - нет

интерпретация: детектор

Во всех случаях значения предиката с использованием двоичного кодирования отождествляется с значением переменной, т.о. переменная заменяет символ предиката Р(х) ~ х

Логические связки &, ù, Ú применяется к событиям и позволяет формулировать составные утверждения в виде формул с предикатами. Связки имеют тот же смысл, что и в логике высказывания.

Пример: работа инкрементного датчика

Ф1Î

/Ф1

Ф2(e,H,L)

\®Ф2

Ф1Î { -положительный фронт; -отрицательный фронт }

Ф2Î{H,L} влево ® Ф1&Ф2 и вправо: Ф1 &ù Ф2 условие формулы

Во всех случаях формула с предикатами является булевой функцией и интерпретация сводится к вычислению булевой функций.

Алгоритм логического управления записывается в виде формул с событиями.

Обычно всегда формула содержит импликацию:

А(х₁,..., х_n) ® В(у) где (х₁,..., х_n) – употребляются только связки &, ù, Ú, ® используется вместо º (для удобства рассуждений)

Предикат В(у) – одномерный исполняемый предикат с двухзначной областью определения.

В(у) ~ у Î{включить, выключить}

{+1, -1}

Пример: в инкрементном датчике включается координата

S – текущее положение, путевая координата

S+:Ф₁ & Ф₂ или то же S-:Ф₁ &ù Ф₂

123 124

+1 -1

Пример управления прессом.

Задача: Включить двигатель (Д), если S₁,S₂,S₃ – выключены и х – замкнуты или у – разомкнут и плунжер двигается вниз.

Запись утверждена:

Д = S₁,S₂,S₃ & (х Ú y&П) – формальное описание алгоритма позволяет выбрать

интерпретацию:

а) аппаратная интерпретация (схема)

б) программная

а) б) МСS51(на ассемблере)

S1 1 & программа:

S2 mov C,S S₁ ® C

S3 orl C,S S₂ Ú C ® C

orl C,S S₃ Ú C ® C

1 Д mov R,C C ® R

mov C,П П ® C

y & anl C,ùy C & ùy ® C

П anl C,x x ® C

anl C,R S & R ® C

mov Д,C C ® Д

2.2 Одномерные предикаты определяющие свойства.

Р(х) = (х<S), х – целые числа

Предикат тождественно истинный, если выполним на всех интервалах, предикат тождественно ложный, если не выполним на всех интерпретациях, предикат выполнимый, если выполняется хотя бы на одной интерпретаций.

Для таких предметов применима теоретико-множественная интерпретация.

W – предметная область, универсум

q(x) – предикат называется характеристической функцией подмножества Q Í W (Q – подмножество значений, где предикат q(x) – истинный)

Q – называется эксистенцыал

Составные утверждения с предикатами формируются с применением логических связок (&, ù, Ú). Формулы имеют теоретико-множественную интерпретацию, называется диаграммами (в частности, Эйлера-Венна).

(которой приписана характеристическая функция)

Определение: Предикат ùr(х) выполним на всех интерпретациях, где r(х) – ложный т.е. не выполним.

r(х) = (х<1) Þ

ù r(х) = ù (х<1) = (х³1)

Определение (коньюнкции): r(x) & q(x)

Пример: Пусть Р(х) = (х делится на 2)

q(х) = (х делится на 5)

Р(х) & q(x) – это формула, область истинности которая совпадает с утверждением «х делится на 10»

Определение: (дизъюнкция) r(x) Ú q(x)

RÈQ

xÎ[0,5 20]

((x > 0,5)Ú(x=0,5)) & (x <20))

(p(x) Ú q(x)) & r(x) пример формулы с предикатом

Правила де Моргана:

ù (р(x) & r(x)) = ù p(x) Ú ù r(x)

на диаграммах

Þ

ù р(x) Ú ù r(x) ~ (P Ç Q)

Определение: (импликация): r(x) ® p(x) ~

ù (r(x) ® p(x)) ~ r(x) – истинно

q(x) – ложно т.е. r(x) & ù p(x)

Þ

r(x) ® p(x) тождественно истинная импликация

изображение экстенсионалов

R c P

~ соотношение между экстенсионалами

Если известны экстенсионалы, то для конечных или бесконечных множеств можно построить экстенсионал формулы с предикатами.

Диаграмма строится для формул, состоящих из не более трех предикатов.

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

Формулы с кванторами для одноместных предикатов.

Определение: формула с квантором всеобщности ("x)Р(х) истина, если на всех значениях на области интерпретации хÎW:

("x) «для всякого хÎW» - квантор всеобщности Р(х) – истинно.

Квантор всеобщности – есть обобщение связки конъюнкции на всю область интерпретации, т.е. ("x)Р(х) = Р(e₁)&Р(e₂)&... &Р(e_n); x_iÎW

Если W-конечно, то тогда квантор – это просто конъюнкция высказывании (составное).

Если W-бесконечно, то ("x) – совершенно новая связка. ("x)Р(х) – высказывание, кот может быть истинным или ложным (оно не имеет теоретико-множественной интерпретации и является просто точкой).

Тождественно-истинное высказывание:

("x)Р(х) = (х + х = 2х) = Т, хÎD - истинно

("x)Р(х) = (2х = 5) = F, хÎD – F – ложно

Определение:

Формула с квантором существования ($x)Р(х): «существует х из W, где Р(х) – истина».

Истинно, если по крайней мере на одном наборе аргументов х – предикат истина.

Квантор существования – обобщение дизъюнкции. Если W – конечная, то ($x)Р(х) = Р(e₁) Ú Р(e₂) Ú... ÚР(e_n); Î{Т,F}; Р(e_i) – высказывание, W – бесконечное множество, то ($x)Р(х) – это высказывание, которое может быть либо истинным, либо ложным.

Пример: ($x)Р(х) = ($x)(х<5) = Т, хÎD

Если переменная х в формуле с предикатом находится в области действия квантора, то она называется связкой. Область действия обозначается либо скобками, либо подчеркиванием.

Если переменная х в формуле с предикатом не находится в области действия квантора, то она называется свободной.

Пример: ("у (($x)Р(х) Ú q(y)) Ú Р(х)

Одна и та же переменная в формуле может быть и связкой и свободной. Формула замкнута, если в ней не существует свободных переменных. Замкнутая формула – это истинное или ложное высказывание. Если в формуле есть свободные переменные, то это функция, истинная или ложная, в зависимости от интерпретации. Высказывание – любая формула, не содержащая свободных переменных. Все формулы с предикатами разделяются на: тождественно-истинные (тавтологии), противоречия, выполнимые. Обозначенные формулы являются законами в логике предикатов. Для доказательства законов необходимо выполнить все интерпретации формул (что не возможно даже для конечных областей интерпретации)

Интерпретация: нужно поставить все возможные условия ® Р(х) ® все значения из Д – области интерпретации.

Теорема 1: Все формулы, содержащие только n – одноместных предикатов, выполнимы или общезначимы на некотором множестве М₁, содержащем не более 2ⁿ элементов.

Р₁(х),Р₂(х)... Р_n(х)

Если n = 1, то |М₂| = 2

n = 2, то |М₁| ~ 4

Доказательство: Пусть задана область интерпретации М (конечная или бесконечная). " Рi(х) – И или Л, это позволяет разделять множество М на 2 эксценсионала:

Каждое из множеств S₀,S₁ можно разделить на подмножество, на которое другой предикат либо И либо Л. Продолжая это разбиение, все множество М можно разделить на систему подмножеств.

М ~ S = { S₀₀₀₀, S₀₀₀₁,..., S₁₁₁₁},

1 2 2ⁿ

в котором предикат р₁(е₁),...,р_n(e_n) принимает значение «И» или «Л», если аргументы выбираются из соответствующих подмножеств.

Если мы выберем систему из n представителей, каждого из множеств, и объединим их в М₁, то мы можем утверждать, что при любой интерпретации, где предикатом:

Р(a_i) = «F» или «Т» = P(aj)/ajÎM₁

где a_i Î S₁

M₁={a₁,..., a_n}

В результате разбиения множества М на классы, получим не более 2ⁿ класса, каждый из которых соответствует одному из 2ⁿ подстановок (выборов), n элементов из М, при которых предиката Р₁(е₁),..., Р_n(е_n) принимают значения «И» или «Л». Оставив только по одному представителю из каждого класса, получим множество представлений М₁, обладающих тем свойством, что для каждого предиката Р_j и любой подстановки элемента a_i.

Р_j(a_i) – найдется представитель из М₁­, на котором значение истинности предикатов совпадает, таким образом формула остается выполнимой или тождественно – истинной на ограниченном множестве М₁, состоящем из не более 2ⁿ элементов.

Таким образом, для интерпретации формулы с одноместными предикатами достаточно выбрать конечное множество, состоящее из произвольных элементов: М₁ = {1,2,..., 2ⁿ}.

Формула от двух предикат.

Ее область интерпретации ® М1 = {1,2}={а,в}

W - универсум

P – экстенсионал для предиката р(х)

Выделяются четыре подмножества:

S00 = ^~P Ç ^~Q

S10 = Q Ç ^~P

S01 = ^~Q Ç P

S11 = Q Ç P

В данном случае n = 2

m = 2² = 4

М₁ = {1,2,3,4} ~ четыре элемента из разных подмножеств (представители подмножеств)

Формула однозначимая, если она истинна на всех интерпретациях.

Для конечных множеств области интерпретации могут быть выбраны с количеством элементов меньше, чем 2ⁿ элементов.

Пример:

1. Только три подмножества:

М₁ = {1,2,3}

2. M₁ = {1,2,3}

3. М₁ = {1,2}

Для интерпретации формулы с одноместными предикатами общего вида:

F{p₁(x₁),..., p_n(x_n), Q}

1) Выбирается область интерпретации Д из 2ⁿ элементов: {1,2,3,..., 2ⁿ}.

2) Каждому предикатному символу P_i(x) ставится в соответствие истинностная функция l_i(2ⁿ), где х Î Д. Мы можем представить ùИ, определяющее всевозможные значения функции: l_i(1), l_i(2),... l_i(2ⁿ), каждому набору аргументов соответствует.

l_i(1) l_i(2) l_i(2ⁿ)

0
0

3) Каждой переменной х_i приписывается значение из множества Д х_i Î Д^~2ⁿ. Это значение подставляем в l_i(х_i) ® l_i(а).

4)Для каждой связанной переменной соответственно формируется конъюнкция, если они связаны квантором всеобщности ", т.е. l(х):

("х)Р(х)® l(1) & l(2) &... & l(2ⁿ)

Общее определение алгоритма:

($х)Р(х) ® l(1) È l(2) È... È l(2ⁿ)

5) Константе присваивается все возможные значения из области Д: QÎД ~2ⁿ значений.

6) Получим составное высказывание и для получения значения истинности нужно выполнить операции: &,Ú,ù,®,~. И получим одно значение этой формулы = «И» и «Л».

На практике пункт 6) выполнять не будем, ограничимся построением формул высказывания. Такой метод, универсальный, конечный и эквивалентен применению ТИ в исчислении высказываний.

Пример: Проверить утверждение (является ли она общезначимой?)

($х)r(х) ® ($х)r(х) – общая формула логики предикатов.

Нужно выполнить интерпретацию

n = 1; m = 2; Д(1,2)

r(x) ~ l(1),l(2)

Подставляем в формулу:

l(1) & l(2) ® l(1) v l(2)

Заменим символы:

1 ~ а; 2 ~ в

l(а) & l(в) ® l(а) Ú l(в)

а,в; l(а); l(в) – события отождествляем с аргументами

а&в ® аÚв – тавтология Þ исходная формула общезначима.

Пример 2: ($х)r(x) ® ("x)r(x)

l(1) v l(2) ® l(1) & l(2)

a Ú в ® a _* d

а_*в Ú ав – выполнимо ® исходное тоже выполнимо.

Пример 3: r(x) & q(x) ® ($x)r(y) & q(x)

n = 2; m = 2² = 4; Д = {1,2,3,4}

r(x) ~ l₁(x) ® l₁(1), l₁(2), l₁(3), l₁(4)

q(x) ~ l₂(x) ® l₂(1), l₂(2), l₂(3), l₂(4)

r(x) & q(x) ® åx₁(i) q(x) Þ система высказываний

l₁(1) & l₂(1) ® å l₁(i) & l₂(1)

l₁(1) & l₂(2) ® å l₁(i) & l₂(2)

..........................

l₁(4) & l₂(4) ® å l₁(i) & l₂(4)

Все высказывания l₁(1), l₁(2),..., l₁(4) независимы, их можно обозначить через а,в,с,д,...; А l₂(1)... l₂(4)... А,В,С,Д

Тогда система функций преобразуется в:

® а Ú `A Ú (a Ú в Ú c Ú d)×A º 1 Þ все является тавтологией Þ исходная общезначима

Утверждение: Для интерпретации формул со свободными переменными х при проверке общезначимости выполнить замыкание формулы квантором всеобщности по этой переменной.

Если переменная в формулу входит связанная и свободная, то в одном из случаев ее стоимость переименовать и выполнить замыкание.

В данном примере на общезначимость проверяется формула:

("х)(r(х))q(x) ® ($y)r(y) & q(x)

Все переменные здесь связаны, поэтому эта формула – высказывание:

(l₁(i) & l₂(i) ® å l₁(j) & l₂(i))

Пример 4: ("х)((Р(х) ® Q & P(y))

y – свободная переменная

х – связанная

("y)("x)((Р(х) ® Q) Ú P(y))

n = 1; m = 2; Д = {1,2}; P(x)~l(1); l(2) ® a,в

1) сначала интерпретируем квантор по х ("x)

("y) ((l(i) ® Q) Ú Q & P(y)) / i = 1,2

("y) (ù l(i) Ú Q Ú Q & P(y))

("y) (ù l(i) Ú Q) = ("y)((ù l(1) Ú Q)(ù l(2) Ú Q))

= Q v а_*в – выполнима – формула не общезначима

2) интерпретация по у ("y)

("х) (Р(х) ® Q Ú Q & l(i)) /i = 1,2

"y (ùP(x) Ú Q)

("x)(ù P(x) Ú Q), (`a Ú Q)(`b Ú Q) = `Q Ú ab

1. Кванторы подчиняются закону коммутативности:

(Kx)(Ky) F(p(x), q(y)) = (Ky)(Kx) F(P(x), q(x))

2. Свойство: расширение области действия кванторов.

1) формулы, содержащие свободные переменные:

Если переменные одинаковые, то одну надо переименовать.

2) формулы, не содержащие свободных переменных:

Р(х)~l₁(1), l₁(2), l₁(3), l₁(4) / М₁ = {1,2,3,4}

а в с d

q(x)~ l₂(1), l₂(2), l₂(3), l₂(4)

A B C D

(a Ú b Ú c Ú d) Ú (A Ú B Ú C Ú D) = (a Ú A) Ú (b Ú B) Ú (d ^ D)

- это тавтология Þ доказано; это доказательство для дизъюнкций.

Все законы логики высказывании распространяются и на логику предикат, в частности, правила де Моргана.

1) свободные переменные:

ù(р(х) & q(y)) = ùp(x) Ú ùq(y)

ù(р(х) & q(x)) = ùp(x) Ú ùq(x)

2) связанные переменные:

ù((Vx) p(x) = ($х)(ùp(x))

Многоместные предикаты (МП)

Если n >> 2, то МП (n – количество переменных)

Р(t₁,... t_n), t₁,... t_n – термы t_j – переменная const из D

t_j – переменная х Î D

t_j – f(x₁, x₂,... x_n): D_n®D

Смысл формулам с предикатами дает интерпретация:

1) задание области интерпретации D; x₁,... x_n Î D

2) символы предикат – n – местные отношения на D;

3) функция f(x₁, x₂,... x_n): D_n®D

4) константа аÎD

Предикат выполним, если n – местное отношение истинно хотя бы на одной подстановке из D. Предикат обозначим, если истинно на всех подстановках. Если в предикате от двух переменных заменить одну значением из области интерпретации, то получим множество предикатов, зависимых только от одной переменной: Р(х,1)... Р(х, к)... Р(х,n), где 1, … к, … n Î D.

Для интерпретации одноместных переменных достаточно 2:

М₁={1,2} ® х,у Î D = М₁ = {1,2}

Для рассмотрения любых n – местных предикат достаточно рассмотреть область интерпретации:

М₁ = {1,... 2ⁿ}

Р(х) ~ l(х₁... х_n) ®

Пример: $х Vу р(х,у) – является ли общезначимой?

М₁ = {1,2} = {а,в}

1) $х (р(х,а) Ú р(х,в)) – применение квантора Vу

2) (l(а,а) & l(a,в)) v (l(в,a) & l(в,в))

А В С D

- после применения квантора $х

А & В v С & D – выполнимая формула Þ исходная формула не общезначима.

Этот способ распространяется на все формулы с одноместными предикатами.

Определение: Теория первого порядка – логическая система с предикатами, аргументы которых не являются предикатами.

Со связками (и, или, не) или их аналогами (ù, Ú, &).

- используются переменные из области интерпретации D.

- возможно использование пустого множества предикатных символов.

- содержит функциональные буквы f(x₁,... x_n).

- содержит множество предикатных const Î D.

Теория – некоторая интерпретация, в которой выполняются законы логики предикатов, используется собственные символы и собственные законы, или аксиомы.

Определение: Теория первого порядка, не содержащая собственных аксиом и символов называется исчислением предикат первого порядка.

Определение: Модель теории первого порядка – всякая интерпретация конкретной теорий, в которой истины все ее законы.

Примеры теорий и моделей:

1. Теория бинарных отношений.

Бинарные отношения - двуместное отношение, которое определяется предикатом.

Характеризуется свойствами:

1) симметричность (a,b)(b,a) Î D (антисимметричность, несимметрична)

2) рефлексивность (а,а) Î D

3) транзитивность

2. Теория строгого упорядочения – используется единственный предикатный символ р(х₁,х₂)

р(х₁,х₂) = х₁ < х₂

ùр(х₁,х₂) = х₁ < х₂

Аксиомы:

1) антирефлекторность "x₁(x₁<х₂)

2) антисимметричность "x₁"x₂(x₁<х₂ Þ х₂ < x₁)

3) транзитивность "x₁"x₂"x₃((x₁<х₂) & (х₂ < x₃) ® (x₁ < x₃))

Модель теорий строгого порядка на множестве целых чисел.

(х < у):D – целые числа {1,2,... n}

Введем двоичное кодирование х = х₁х₂х₃ у = у₁у₂у₃

(х < у) = ((х₁х₂х₃) < (у₁у₂у₃)) = x₁ < y₁ v (x₁ < y₁) & (x₂ < y₂ v x₂ < y₂ & x₃ < y₃)

`x<sub>1</sub>y<sub>1</sub> Ú `x₁ `y<sub>2</sub> & (`x₂y₂ Ú `x<sub>2</sub> `y₂ `x₃y₃)

Расширение области действия предиката.

- формула замкнута:

Кх р(х) Ú Kx q(x)? K(x)(p(x) Ú q(x))

1) ограничимся квантором существования:

$х р(х) Ú $х q(x)? $х(p(x) q(x))Ú

рассмотрим отдельно левую часть:

å l₁(i) Ú ål₂(i) = a Ú в Ú c Ú d Ú A Ú B Ú C Ú D

М₁ = {1,2,3,4}

для l₁(i) = а b с d для l₂(i) = А В С D

рассмотрим отдельно правую часть:

$х (р(х) Ú q(x)) = å (l₁(i) Ú ål₂(i)) = (a Ú А) Ú (в Ú B) Ú (c Ú C) Ú (d Ú D) =

=a Ú b Ú c Ú d Ú A Ú B Ú C Ú D

2) проверим квантор всеобщности:

"x p(x) Ú "x q(x)? "x (p(x) Ú q(х))

левая часть:

"x p(x) Ú "x q(x) = l₁(i) Ú l₂(i) = аbсd Ú ABCD

правая часть:

"x (p(x) Ú q(x)) = (l₁(i) Ú l₂(i)) = (а Ú A)(b Ú B)(с Ú C)(d Ú D)

Для левой части:

(а Ú A)(а Ú B)(а Ú C)(a Ú D)... (d Ú A)(d Ú B)(d Ú C)(d Ú D) = f & F

По правилу удаления конъюнкции: f & F ® F Þ тавтология

т.е. получим, что вместо? нужно поставить знак импликации (®)

"x p(x) Ú "x q(x) ® "x (p(x) Ú q(х))

Аналогично можно выразить и другие формулы.

Пример:

Кх р(х) Ú Kx q(x)? K(x)(p(x) Ú q(x))

"x p(x) & "x q(x) = "x (p(x) & q(х))

$х р(х) & $х q(x) $х(p(x) & q(x)

Интерпретируем выражение: (х < у) = (х₁х₂х₃ < у₁у₂у₃) Þ на множестве двоичного кода Þ х₁ < у₁ v (х₁ = у₁ v х₂ = у₂ (х₃ < у₃))

Пример: (х<5)(х₁х₂х₃ < Æ101) Þ (х < y)=x₁ < y₁ v (x₁ = y₁)(x₂ <y₂ v x₂ = y₂(x₃ < y₃))

Þ x₁ v x₁(Æ v x₂x₃) = x₁ v x₂x₃ ® схема ® программа