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

Функциональная полнота

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

1. Несохранение 0 ( f(0, 0, ..., 0) = 1)

2. Несохранение 1 ( а(1, 1, ..., 1) = 0)

3. Не самодвойственность.

f(X₁,X₂,...,X_n) ¹ f(X₁,X₂,...,X_n)

4. Немонотонность.

a₁×a₂×...×a_n ³b₁×b₂×...×b_n

f(a₁,a₂,...,a_n)<f(b₁,b₂,...,b_n)

5. Нелинейность.

Функция называется нелинейной, если она не может быть представлена в виде :

a₀ Å a₁x₁ Å a₂x₂ Å...,

где a_i = 1 или 0

Примеры линейных функций:

1 Å X = X

a₀ = 1

a₁ = 1

a_2..¥ = 0

X Å Y - неравнозначность.

a₀ = 0

a₁ = 1

a₂ = 1

a_3..¥ = 0

Функционально полные наборы создают, например:

Ø и &; Ø и Ú; Ø и ®. Операции штрих Шеффера½ и стрелка Пира ¯ каждая в отдельности образуют функционально полный набор.

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

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

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

Операции:

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

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

Язык предикатов - наиболее приближенный к естественным языкам формальный математический (логический) язык.

В логике предикатов к операциям, имеющим место в логике высказываний, добавляются операции навешивания кванторов.

" - квантор общности. "x P(x) - "для всех х - P(x)".

$ - квантор существования. $x P(x) - "есть такие х, что P(x)".

( $! или $₁ - существует и притом единственный).

Кванторы связывают соответствующие переменные. Связанные переменные можно воспринимать как константы, а несвязанные переменные - свободные переменные -

как собственно переменные.

Содержательные примеры предикатов :

R(x) - х любит кашу (одноместный предикат).

"x R(x) - все любят кашу (нульместный предикат - высказывание).

$x R(x) - некоторые (есть такие) х любят кашу.

L(x, y) - х любит y (двухместный предикат).

$x"y L(x, y) - Существует x, который любит всех y.

"x ( C(x) ® O(x) ) - Все студенты C(x) отличники O(x).

$x ( C(x) & O(x) ) - Некоторые студенты C(x) отличники O(x).

Здесь есть повод поразмышлять об использовании операций ® и & в двух последних высказываниях.

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

Пусть х Î{a₁, a₂, ... , a_n}

"x P(x) = P(a₁) & P(a₂) & ... & P(a_n).

$x P(x) = P(a₁) Ú P(a₂) Ú ... Ú P(a_n).