ФОРМУЛА ЛОГИКИ ПРЕДИКАТОВ И ЕЕ ЗНАЧЕНИЕ.. Реферата Теория. Основные понятия, связанные с предикатами Равносильные формулы логики предикатов

• Название: Реферата Теория. Основные понятия, связанные с предикатами Равносильные формулы логики предикатов
• Дата: 04.05.2019
• Размер: 1.38 Mb.
• Имя файла: ФОРМУЛА ЛОГИКИ ПРЕДИКАТОВ И ЕЕ ЗНАЧЕНИЕ..docx
• Тип: Реферат; #76075

ПЛАН РЕФЕРАТА:

1. Теория. Основные понятия, связанные с предикатами

2. 
   Равносильные формулы логики предикатов
   

3. 
   Таблица формул алгебры предикатов. Законы логических операций
   

4. 
   Примеры задач с использованием формул логики предикатов
   

5. 
   Решение задач по математической логике - исчисление предикатов
   

ТЕОРИЯ. ОСНОВНЫЕ ПОНЯТИЯ, СВЯЗАННЫЕ С ПРЕДИКАТАМИ
В логике предикатов используется следующая символика:

1. 
   Символы р,q,r,... — переменные высказывания, принимающие два значения: 1 — истин 0 — ложь.
   

2. 
   Предметные переменные - х,у,z.....которые пробегают значения из некоторо множества М:х°, у°,z°,... - предметные константы, то есть значения предметн переменных;
   

3. 
   Р(· ), f( · ) - одноместные предикатные переменные; Q(·,·,...,·), R(·,·,...,·) - n- местны предикатные переменные. Р°(· ), Q°(·,·,...,·) - символы постоянных предикатов.
   

4. 
   Символы логических операций:
   

5. 
   Символы кванторных операций: .
   

6. 
   Вспомогательные символы: скобки, запятые. Определение 1. (формулы логики предикатов).
   

1. Каждое высказывание как переменное, так и постоянное, является формулой.

2. 
   .Если F(·,·,...,·) - n-местная предикатная переменная или постоянный предикат, ax_1tx₂,..., хпредметные переменные или предметные постоянные, не обязательно все различны то F(x_1,x₂,...,х_n)есть формула. В этой формуле предметные переменные являются свобо ными. Формулы вида 1 и 2 называются элементарными.
   

2. 
   .Если Аи В - формулы, причем такие, что одна и та же предметная переменная не являет в одной из них связанной, а в другой свободной, то Av В, А&В,А→ Весть формулы. В эт формулах те переменные, которые в исходных формулах были свободными, являют свободными, а те, которые были связанными, являются связанными.
   

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

5. 
   Если -А(x) - формула, в которую предметная переменная хвходит свободно, то слова А(х)и А(х)являются формулами, причем предметная переменная в них входит связанно.
   

5. 
   Никакая другая строка символов формулой не является.
   

РАВНОСИЛЬНЫЕ ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ.

Определение1.Две формулы логики предикатов А и В называются равно сильнымина
о бластиМ,если они принимают одинаковые логические значения при всех значениях входящ в них переменных, отнесенных к области М.

Определение2.Две формулы логики предикатов А и В называются равно сильными, если он равносильны на всякой области.

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, н содержащая х). Тогда имеют место равносильности:

1.

2.

3.

4
5.

6. .

7.

8.

9.

10.

11.

12.

13.

14.

15.
Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной .
Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной .
Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих и частей взять отрицания и воспользоваться законом двойного отрицания.

ЗАКОНЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ.

(общезначимые формулы логики предикатов)

Равносильныеформулылогикипредикатов.

Определение1.Две формулы логики предикатов А и В называются равно сильнымина
о бластиМ,если они принимают одинаковые логические значения при всех значениях входящ в них переменных, отнесенных к области М.

Определение2.Две формулы логики предикатов А и В называются равно сильными, если он равносильны на всякой области.

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, н содержащая х). Тогда имеют место равносильности:
1.


2.


3.

4.

5.

6. .


7.


8.


9.


10.


11.


12.


13.


14.


15.

Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной .

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной .

ПРИМЕРЫ ЗАДАЧ

С ИСПОЛЬЗОВАНИЕМ ФОРМУЛ ЛОГИКИ ПРЕДИКАТОВ


Пример 1. Какие из следующих выражений являются формулами логики предикатов? каждой формуле выделите свободные и связанные переменные.

1)		;
2)	;
3)	;

4);
5);
6).
Решение. Выражения 1), 2), 4), 6) являются формулами, так как записаны в соответствии определением формулы логики предикатов. Выражения 3) и 5) не являются формулами. выражении 3) операция конъюнкция применена к формулам Р(х) и; в первой из н переменнаях свободна, а во второй связана квантором общности, что противореч определению формулы. В выражении 5) квантор существования по переменной унавешен формулу , в которой переменнаяусвязана квантором общности, что также против речит определению формулы.
В формуле 1) переменная у свободна, а переменные х и zсвязаны. В формуле 2) н предметных переменных. В формуле 4) переменная хсвязана, а переменная усвободна.
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда зада множество М,на котором определены входящие в эту формулу предикаты. Логическ значение формулы логики предикатов зависит от значения трех видов переменных, входящ в формулу:
а) переменных высказываний;
б) свободных предметных переменных из множества М; в) предикатных переменных.

При конкретных значениях этих переменных формула принимает конкретное логическ значение.
Пример 2. Дана формула ,где предикаты Р(х),Q(х) и R(х) определен на множестве N. Найти ее значение, если

1. 
   Р(х): «число хделится на 3», Q(x):«число хделится на 4», R(x):«число хделится на 2»;
   
2. 
   Р(х):.«число хделится на 3», Q(x):«число хделится на 4», R(x):«число хделится на 5». Решение. В обоих случаях конъюнкция Р(х)&Q(х) есть утверждение, что число хделится
   

12. Но тогда при всех х,если число хделится на 12, то оно делится и на 2, и, значит, в случае формула истинна.
Так как из делимости числа хна 12 не при всех хследует делимость числа хна 5, то в случ

2. 
   формула ложна.
   

Пример 3. Вычислить значение формулы
,если предикат Р(х,у)имеет значение Р°(х,у) —«число хмень числа у»и определен на множестве .
Решение. Так как при указанном значении предиката Р(х,у)высказывание означает утверждение, что для любого натурального числа х найдется натуральн
число у,большее числа х,то это высказывание истинно. В то же время высказывани означает утверждение, что существует натуральное число х,которое мень любого натурального числа у.которое ложно. При этом исходная формула, очевидно, ложна.
Определение 2. Две формулы логики предикатов А и Вназываютсяравносильными областиМ,если они принимают одинаковые значения при всех значениях входящих в н переменных, отнесенных к области М.
Две формулы логики предикатов Аи Вназываютсяравносильными,если они равносильны всякой области.

Здесь, как и в алгебре высказываний, для равносильных формул принято обозначение А≡В Ясно, что все равносильности алгебры высказываний будут верны, если в них вмес

переменных высказываний подставить формулы логики предикатов. Но, кроме того, име место равносильности самой логики предикатов. Сюда, в первую очередь, следует отнес равносильности:
, .
Они широко используются в логике предикатов при равносильных преобразованиях, ес приходится иметь дело с выражениями, содержащими операцию отрицания.
Пример 4. Найти отрицание следующих формул: 1) ;

2) ;
3).
Решение. 1);

2)

2. 
   ;
   

Доказательство равносильностей логики предикатов требует или детального рассмотрен значений формул или использования известных равносильностей.
Пример 5. Доказать равносильность
.
Решение. Для доказательства равносильности достаточно рассмотреть два случая:

1. 
   Пусть предикаты А(х) и в(х) тождественно ложны. Тогда будет тождественно ложным предикат . При этом будут ложными высказывания
   

.

2. 
   Пусть теперь хотя бы один из предикатов (например, А(x)) не тождественно ложный. Тог будет не тождественно ложным и предикат A(x) v B(x) . При этом будут истинны высказывания и ,а, значит, буд истинными висходные формулы.
   

Следовательно,.
Пример 6. Доказать равносильность
.
Решение. Рассмотрим два случая:

1. 
   Пусть высказывание сложно. Тогда для любого предиката А(х) будет тождественно ложны высказывание и предикатc&А(х) ,и , следовательно, высказывание
   

. Значит, в этом случае обе исходные формулы тождественно ложны.

2. 
   Пусть теперь высказывание систинно. Тогда, очевидно, значения исходных формул буд целиком зависеть от значений предиката А(х). Если А(х) - тождественно истинный предикат, будет тождественно истинным и предикат с& А(х), и, следовательно, будут тождествен истинными высказывания , , , то есть тождественно истинн исходные формулы. Если же предикат А(х) не тождественно истинный, тогда будет тождественно истинным предикат с&А(х), а высказывания ,
   

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

13. 
    Укажите, какие из следующих выражений являются формулами логики предикатов. каждой формуле выделите свободные и связанные переменные:
    

1)	;
2)	;
3)			;
4)	;
5)	;
6)		.

13. 
    Даны утверждения А(n): «число n делится на 3», В(п):«число n делится на 2», С(
    

«число пделится па 4», D(n)«число n делится на 6», Е(п): «число n делится на 12». Укажит какие из следующих утверждений истинны, какие ложны:
1) ;
2);
3);
4);
5);

13. 
    Пусть предикатР(х,у)определен на множестве М= N × N и означает « х<у».
    

1. 
   Какие из следующих предикатов тождественно истинные и какие тождественно ложные:
   

2. 
   Для тех предикатов из 1), которые не являются ни тождественно истинными, тождественно ложными, указать область истинности и область ложности.
   

3. 
   Какие из следующих предложений истинны и какие ложны:
   

13. 
    Показать, что кванторы общности и существования не перестановочны, то есть высказывания и могут, вообще говоря, иметь различные значения.
    

13. 
    Среди следующих пар предикатов выберите те, в которых предикаты являют отрицаниями друг друга:
    

1. 
   «а < b» и «b<а»;
   

1. «Треугольник ABCпрямоугольный» и «Треугольник ABCтупоугольный»;

3. 
   «Целое число kчетно» и «Целое число kнечетно»; 4) «Функция f нечетна» и «Функция четна»;
   

5) «Натуральное число n- простое» и «Натуральное число n - составное.»

13. 
    Доказать следующие равносильности: 1)
    

2)
3)
4)
5)
6)
7)
8)
9)
10)
11)

13. 
    Найти отрицания следующих формул: 1)
    

2)
3)
4)
5)
6)

13. 
    Пусть предикат А(х)иВ(х)- любые предикаты. Kакие из следующих формул равносильн формуле (*)?
    

13. 
    Доказать, что для любой формулы логики предикатов можно построить ей равносильну формулу, не содержащую:
    

кванторов существования; кванторов общности. 3.22. Доказать, что формулы	и	не равносильны.
3.23. Доказать, что формулы	и	не равносильны.
3.24. Доказать, что 1)
2) то же с заменой & на v;

3) можно ли в 1) и 2) заменить F(x) и G(y)двухместными предикатами, зависящими от x и y?

25. 
    Пусть А(х) и В(х) два одноместных предиката, определенных на множестве М таких, ч высказываниеистинно. Доказать, что высказыван ложно.
    

25. 
    Даны два предиката Q(х,у)и R(y,z),определенные на множестве М× М, где М= {а, b,с Для следующих предложений записать их выражения без использования кванторн операций:
    

25. 
    Каким условиям будут удовлетворять области истинности предикатов А(х) и В( определенных на множестве М,если истинны высказывания:
    

Решение задачи по математической логике Исчисление предикатов

Дано универсальное множество = {e,d,f,c,g,a,h,b,o,u,l} и два подмножества J={f, b, g, h, a, c} и I={o, h, b, l, u, a};
два предиката C(x)=" x принадлежит J" и В(x)=" x принадлежит I".
Найдите область истинности предикатов:
P1(x)=C(x)∨B(x); P2(x)=C(x)→B(x); P3(x)=C(x)B(x); P4(x)=C(x)&B(x)


Решение.
Универсальное множество U = {e, d, f, c, g, a, h, b, o, u, l}. Область истинности предиката С(x): J={f, b, g, h, a, c}. Область истинности предиката B(x): I={o, h, b, l, u, a}.

Область истинности предиката P1(x)=C(x)∨B(x):

J⋃ I={f, b, g, h, a, c, o, l, u}.

Область истинности предиката P2(x) = C(x)→B(x):

J I(U\ J)  I
={e, d, o, u, l}⋃{o, h, b, l, u, a}={e, d, o, u, l, h, b, a}.

Т.к. C( x) ∼ B( x) (C(x) B( x)) & (C( x) B(x)) , то область истинности предиката P3(x)=C(x)B(x) – это элементы, принадлежащие области пересечения множеств J∩ I(оба предиката при этих элементах истинны), и элементы, не принадлежащие ни одному из этих множеств (оба предиката при этих элементах ложны): {e, d, a, h, b}.
Область истинности предиката P4(x)=C(x)&B(x):
J∩ I= {b, h, a}.

2. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов наименьшей местности. Привести формулу к предваренной нормальной форме:

«Через две различные точки проходит единственная прямая»

Решение. Введем элементарные предикаты наименьшей местности

^P^x^^{xточка}<sup>,

L</sup>^x^^{xпрямая}<sup>,

B</sup>^{x, y}^^{х проходит через у}<sup>,

N</sup>^{x, y}^^{х не совпадает с у}^.

Тогда формулу «Через две различные точки проходит единственная прямая»

можно записать в следующем виде:

_xyP_x_P_y_N_x, y_⇒

⇒ z_L_z_B_z, x_B_z, y_w_L_w_B_w, x_B_w, y_⇒ N_z, w_

То есть для любых двух не совпадающих точек

x, yсуществует прямая z,

которая проходит через данные точки и любая прямая w, также проходящая через эти точки, совпадает с z (то есть z единственная такая прямая).

Приведем формулу к предваренной нормальной форме. Исключаем импликации:

_xyP_x_P_y_N _x, y_

• 
  _z_L_z_B_z, x_B_z, y_w_L_w_B_w, x_B_w, y_N_z, w_
  

Заносим отрицания до атомарных формул.

xy_P_x_P_y_N_x, y_

• 
  _z_L_z_B_z, x_B_z, y_w_L_w_B_w, x_B_w, y_N_z, w_
  

Задача скачана с сайта www.MatBuro.ru

Еще примеры: https://www.matburo.ru/ex_subject.php?p=dm

©МатБюро - Решение задач по математике, экономике, статистике
^xy_^P^x^P^y^N^{x, y}_^

• 
  _z_L_z_B_z, x_B_z, y_w_L_w_B_w, x_B_w, y_N_z, w_
  

Переименовываем связанные переменные. Нет необходимости.

^xy_^P^x^P^y^N^{x, y}_^

• 
  _z_L_z_B_z, x_B_z, y_w_L_w_B_w, x_B_w, y_N_z, w_
  

Переносим кванторы в начало формулы.

^{xyzw}_^P^x^P^y^N^{x, y}_^

• 
  _L_z_B_z, x_B_z, y__L_w_B_w, x_B_w, y_N_z, w_
  

Получили предваренную нормальную форму.

Задача 3. Составить предваренную нормальную форму:

x_yP_x, y_yP_y, x_y_Q_x, y_Q_y, x_& zP_z_

Решение.

Применяем алгоритм приведения к ПНФ, используя законы логики предикатов:

^P^{x, y}^P^{y, x}

Переименовываем переменную:

^yP^{y, x}^y₂ ^P^y₂ ^{, x}

Преобразуем:

x_y₁P_x, y_{1 }y₂ P_y₂ , x_y_{1 }Q_x, y_{1 }Q_y₁ , x_& zP_z_
Далее преобразуем импликации: PQPQ

Преобразуем:

x_y₁P_x, y_{1 }y₂ P_y₂ , x_y_{1 }Q_x, y_{1 }Q_y₁ , x_& zP_z_

убираем двойное отрицание

x_y₁P_x, y_{1 }y₂ P_y₂ , x_y_{1 }Q_x, y_{1 }Q_y₁ , x_& zP_z_

^Q^{x, y}₁ ^Q^y₁^{, x}

x_y₁P_x, y_{1 }y₂ P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

Продвигаем отрицания вглубь

x_y₁P_x, y_{1 }y₂ P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

x_y₁P_x, y_{1 }y₂P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

x_y₁P_x, y_{1 }y₂P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

x_y₁P_x, y_{1 }y₂P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

Выносим кванторы.

x_y₁P_x, y_{1 }y₂P_y₂ , x_y_{1 }Q_x, y_{1 }& zP_z_

xy₁y_{2 }P_x, y_{1 }P_y₂ , x_y₁z_Q_x, y_{1 }& P_z_

xy₁y₂z_P_x, y_{1 }P_y₂ , x_Q_x, y_{1 }& P_z_

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

Какие вхождения переменных являются свободными,а какие связанными в следующей формуле: ^{∀ ( , ) → ∀ ( ).}
Решение
Переменные, не связанные квантором, называют свободными переменными.

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

( , ), ∀ и ( )).
Анализируя действия кванторов и количество вхождений переменных, можно определить, что:

1. 
   Все два вхождения переменной (∀ , ( , )) являются
   

связанными, так как квантор ∀ действует на выражение ( , ).

2. 
   Из трех вхождений переменной первое вхождение ( , ) является свободным, а два остальных (∀ и ( )) являются связанными, так как квантор ∀ действует на выражение ( ).