Шпаргалка по "Программированию и компьютерам"

 6. Высказывания. Логические связки с высказываниями. Тождественно-истинные формулы. Правильные рассуждения. Проблема разрешимости в алгебре высказываний.

1. Высказывания

 Высказывание  – предложение, относительно которого можно сказать, истинно оно или  ложно. Пример: «Москва – столица России».

2. Логические связки с высказываниями

 Их 6 (см. таблицу):

 

 1) отрицание,  «не» ( Ø );новое выс-ие явл-ся истинным если выс-и ложно и наоборот

 2) конъюнкция, «и», «а», «но» ( & ); оба выск-я  истины то истина в других  случаях лож

 3) дизъюнкция, «или» в неразделительном смысле ( Ú ); если хотя бы одно истнина то истина

 4) импликация, «если, то» ( ® ); если х истина а y лож то лож в остальных иcтина

 5) эквиваленция, «тогда и только тогда, когда» ( « ); Считаются истины когда оба когда оба выск-я одновре-но либо ист либо лож

 6) сложение  по модулю 2, «или» в разделительном  смысле ( Å ).

3. Тождественно-истинные формулы

 Тождественно  истинная формула (тавтология) – формула, являющаяся истинной на любой оценке списка своих переменных (x₁, …, x_n), например, (A Ú ØA).

 Выполнимая  формула – формула, являющаяся истинной хотя бы для одной оценки списка своих переменных (x₁, …, x_n). Опровержимая формула – формула, являющаяся ложной хотя бы для одной оценки списка своих переменных (x₁, …, x_n). Тождественно ложная формула – формула, являющаяся ложной на любой оценке списка своих переменных (x₁, …, x_n).

4. Правильные рассуждения
1. Определение

 Правильное  рассуждение – рассуждение, в котором из конъюнкции посылок следует заключение, т.е. являющееся истинным в случае истинности посылок. Схема рассуждения: (P₁ & … & P_n) ® D, где P₁, …, P_n – посылки, D – заключение. Истинность заключения не является критерием правильности рассуждения.

2. Правила

 1) Заключения (Modus Ponens): (A ® B, A) ® B;

 2) Отрицания (Modus Tollens): (A ® B, ØB) ® ØA;

 3) Утверждения  отрицания: (A Å B, A) ® ØB;

 4) Отрицания  утверждения: (A Ú B, ØA) ® B;

 5) Транзитивности: (A ® B, B ® C) ® (A ® C);

 6) Закон противоречия: (A ® B, A ® ØB) ® ØA.

5. Проблема разрешимости в алгебре высказываний
1. Формулировка

 Существует  ли алгоритм, который позволил бы для  любой формулы алгебры высказываний установить, является ли она тождественно истинной или нет?

2. Решение

 Формула является тождественно истинной тогда и только тогда, когда в её КНФ каждый конъюнктивный член представляет собой элементарную дизъюнкцию, которая содержит некоторую переменную и её отрицание. Формула является тождественно ложной тогда и только тогда, когда в её ДНФ каждый дизъюнктивный член представляет собой элементарную конъюнкцию, которая содержит некоторую переменную и её отрицание. Доказать тождественную истинность (ложность) формулы также можно, составив таблицу истинности. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 7. Предикаты. Понятие предиката. Логические операции с предикатами. Операции с кванторами. Свободные и связанные переменные. Формулы логики предикатов. Интерпретация формул. Равносильность формул. Приведённая и нормальная формы формул.

6. Предикаты. Понятие предиката

 Одноместный предикат P(x) – одноместная функция, принимающая значения из множества B = {0, 1}, когда x (предметная переменная) пробегает множество M (предметную область). Пример: x – столица России, M = {Москва, Тюмень, Париж}. Область истинности предиката (I_p) – все x из M, для которых предикат принимает истинное значение. N-местный предикат P (x₁,…,x_n) – N-местная функция, принимающая значения из множества B = {0, 1}, когда её аргументы пробегает множество M.

7. Логические операции с предикатами

 Их 5 (см. таблицу):

 1) отрицание  ( Ø );

 2) конъюнкция ( & );

 3) дизъюнкция ( Ú );

 4) импликация  ( ® );

 5) эквиваленция ( « );

8. Операции с кванторами

 Их 2:

 1) Квантор  общности ( " ). Выражение "x P(x) истинно, если P(x) истинно для всех x из M, иначе "x P(x) ложно;

 2) Квантор  существования ( $ ). Выражение $x P(x) истинно, если P(x) истинно хотя бы для одного x из M, иначе $x P(x) ложно.

9. Свободные и связанные переменные

 Связывание  переменной – переход от P(x) к выражению "x P(x) или $x P(x) [т.е. навешивание квантора на предикат]. Связанная переменная – переменная, на которую навешан предикат. Свободная переменная – переменная, от которой зависит значение предиката.

10. Формулы логики предикатов

 Алфавит алгебры  предикатов содержит предметные переменные, предикатные символы, логические связки, символы кванторов и скобки. Формула  – слово в языке, порождённом  КС грамматикой со следующими правилами:

 I ® S(x₁, …, x_n), S ® P, S ® Q, …, I ® (ØI), [ I ® ( I & I ), I ® ( I Ú I ), I ® ( I ® I ), I ® ( I « I ) ](Недопустимо наличие переменной, являющейся свободной в одной половине формулы и связанной – в другой), [ I ® ( "x_i I ), I ® ( $x_i I ) ](Необходимо, чтобы x_i была свободной в I).

 Пример: $x₁ P(x₁, x₂) & Q(x₂).

11. Интерпретация формул

 Интерпретация формулы – совокупность, состоящая  из множества M и соответствия f, которое сопоставляет каждому предикатному символу формулы соответствующий предикат.

12. Равносильность формул
1. Определение

 Пусть формулы  F и G имеют одно и то же множество свободных переменных. Тогда F и G равносильны:

 1) в данной  интерпретации – если на любом  наборе свободных переменных  они принимают одинаковые значения;

 2) на множестве  M – если они равносильны в любой интерпретации, заданной на этом множестве;

 3) в алгебре  предикатов – если они равносильны  на любом множестве M.

2. Основные равносильности

 1) Перенос  квантора через отрицание: Ø ("x P(x)) º $x Ø P(x); Ø ($x P(x)) º "x Ø P(x);

 2) Вынос квантора за скобки: "x A(x) & B º "x (A(x) & B); "x A(x) Ú B º "x (A(x) Ú B); $x A(x) & B º $x (A(x) & B); $x A(x) Ú B º $x (A(x) Ú B); "x A(x) & "x B(x) º "x (A(x) & B(x)); $x A(x) Ú $x B(x) º $x (A(x) Ú B(x));