Содержание
- 2. Изучить литературу. Прослушать лекцию. Разработать конспект.
- 3. Если дана некоторая формула F и каждой ее пропозициональной переменной приписано значение "и" или "л", то
- 4. Отношение равносильности формул
- 5. Определение. Две формулы F1 и F2 называют равносильными (F1 ≡ F2), если они имеют одинаковое значение
- 6. Истинностные функции
- 7. Совершенные нормальные формы истинностных функций функций
- 8. Дизъюнктивная и конъюнктивная нормальные формы формулы (ДНФ и КНФ). Формулы, построенные особым образом из высказывательных переменных
- 9. Дизъюнктивная и конъюнктивная нормальные формы формулы (ДНФ и КНФ). ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИЕЙ называется конъюнкция некоторых высказывательных переменных
- 10. Формула F называется КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (КНФ) от высказывательных переменных системы, если она является конъюнкцией элементарных
- 11. Совершенные нормальные формы удобно записывать, используя таблицы истинности, по значениям пропозициональных переменных и значению описываемой формулы.
- 12. Совершенные нормальные формы удобно записывать, используя таблицы истинности, по значениям пропозициональных переменных и значению описываемой формулы.
- 13. Пример. Записать СДНФ и СКНФ для функции, заданной таблицей истинности.
- 14. Пример. Записать СДНФ и СКНФ для функции, заданной таблицей истинности. a) Формула СДНФ: F(A,B,C) = =(⎤А∧⎤B∧⎤C)∨(⎤А∧B∧⎤C)∨(А∧⎤B∧⎤C)∨(А∧B∧C);
- 15. Полные системы истинностных функций
- 16. Система истинностных функций называется полной, если с помощью функций этой системы можно выразить любую истинностную функцию.
- 17. . Формулы Общезначимая (тавтология, тождественно истинная ╞ ) Невыполнимая (противоречие, тождественно невыполнимая) Нейтральная Выполнимая Необщезначимая
- 18. . Важнейшие общезначимые формулы.
- 19. Формула, построенная на пропозициональных букв А1, А2, …, An и их отрицаний ¬А1, ¬А2, …, ¬An
- 20. Предложение 1. Формула ╞E, построенная на атомах Р1, Р2, …, Рn , тогда формула ╞Е*, полученная
- 21. (Подстановка вместо атомов.) Предложение 1 Пусть Е - формула, в которую входят только атомы Р1,...., Рn
- 22. Предложение 2. Если ╞А и ╞А→В, то ╞В.
- 23. Предложение 3. ╞А↔В тогда и только тогда, когда А≡В.
- 24. Предложение 4. ╞Е тогда и только тогда, когда ¬Е – противоречие.
- 25. (Подстановка вместо атомов.) Предложение 2 Если ╞ А и ╞ А→В, то ╞ В. Предложение 3
- 26. Пример. Пусть А есть ¬А˄(¬В∨С), тогда ¬А≡А∨ (В˄¬С). Упражнение. Постройте формулы отрицания : (1) (А ∨¬В)
- 27. Предложение. (принцип двойственности). Пусть А и В – формулы такого же вида, что и в предложении
- 28. Пример. А =(А ˄¬А) ╞¬А ╞¬(А ˄¬А) ; ╞ А+ ╞ ¬А∨А; ╞ А* ╞ ¬¬A∨¬A;
- 29. Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.
- 30. Важнейшие общезначимые формулы Теорема. Следующие формулы алгебры высказываний являются тавтологиями: Закон исключенного третьего Закон отрицания противоречия
- 32. . Лекция 4 1..Исчисление высказываний. 2. Понятие булевой функции. 3. Элементарные функции. ДНФ и КНФ. 4.
- 33. Умозаключение - это мысль, в ходе которой из одного или нескольких суждений выводится новое суждение. При
- 38. Важнейшие правила следования. 16. Если Г |=¬( А ∨В), то Г |= ¬А˄¬В. (Удаление отрицания дизъюнкции
- 39. Важнейшие правила следования. 20. Если Г |= А →В, то Г |= ¬В→¬А. (Контрапозиция К). 21.
- 40. Важнейшие правила следования. 24. Если Г |= А˄В→С, то Г |= А→(В→С). (Разъединение посылок РП). 25.
- 41. 1. Дано F=(F1→F2) →((F2→F3) →(F1∨F2 →F3). Выполнить преобразования для упрощения алгебраического выражения. Удалить всюду логическую связку
- 42. 2. Дано F=⎤(F1→F2)∧(⎤F3∨⎤F4)∨⎤(F1∨F2)∧⎤(F3∧F4). Выполнить эквивалентные преобразования для упрощения алгебраического выражения. Удалить логическую связку “→”: F=⎤(⎤F1∨F2)∧(⎤F3∨⎤F4)∨⎤(F1∨F2)∧⎤(F3∧F4); Опустить
- 43. Алгоритм приведения к нормальной форме Шаг 1. Устранить логические связки “↔” и “→” всюду по правилам:
- 44. Алгоритм приведения к нормальной форме Шаг 2 Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:
- 45. Алгоритм приведения к нормальной форме Шаг 3 Применить закон дистрибутивности: для КНФ: F1∨(F2 ˄F3) = (F1∨
- 46. Пример: Дана формула F=((F1→(F2∨⎤F3))→F4). Привести формулу к виду КНФ: 1) F=(⎤F1∨(F2∨⎤ F3))→F4 ; 2) F=⎤(⎤F1∨(F2∨⎤F3))∨F4 ;
- 47. Пример: Дана формула F=(⎤(F1∧F2)(F1∨F2)). Привести формулу к виду ДНФ: F=(⎤F1∨⎤F2)˄(F1∨F2); F=((⎤F1∨⎤F2)∧F1)∨ ((⎤F1∨⎤F2) ∧ F2); F=(⎤F1 ∧
- 48. Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула
- 49. Алгоритм преобразования ДНФ к виду СДНФ. Шаг 1: если в элементарную конъюнкцию F не входит подформула
- 50. Преобразовать формулу к виду СДНФ: F=F1∧⎤F2∧(F3∨⎤F3) ∨ F1∧⎤F3∧F4˄(F2∨⎤F2) ∨F1˄F2˄F3˄⎤F4; 1) F=F1∧⎤F2∧F3∨F1∧⎤F2∧⎤F3∨F1∧F2∧⎤F3∧F4∨F1∧⎤F2∧⎤F3∧F4∨ F1∧F2∧F3∧⎤F4; 2) F=F1∧⎤F2∧F3∧(F4∨⎤F4)∨F1∧⎤F2∧⎤F3∧(F4∨⎤F4)∨F1∧F2∧⎤F3∧F4∨ F1∧⎤F2∧⎤F3∧F4∨ F1∧F2∧F3∧⎤F4;
- 51. Пример. Дано F=(F1∨F2)∧(⎤F1∨⎤F2∨F3∨F4). Преобразовать формулу к виду СКНФ. 1) F=(F1∨F2∨F3∧⎤F3) ∧(⎤F1∨⎤F2∨F3∨F4); 2) F=(F1∨F2∨F3) ∧(F1∨F2∨⎤F3) ∧(⎤F1∨⎤F2∨F3∨F4); 3)
- 52. Примеры. Определить, к какому классу относятся формулы: a) F = ((A→B)∧(A→C)→(A→(B∧C))
- 53. б) F=A∧ (⎤B∨⎤C) ∧(A→B) ∧ (A→C)
- 54. Любая формула исчисления высказываний может рассматриваться как формула алгебры высказываний и, следовательно, можно рассматривать ее логические
- 55. Пример: В семье есть договоренность относительно пользования телевизором на субботние вечера: а) если не смотрит отец(⎤А),
- 56. Логическое следствие Теорема . (признак логического следствия). Формула H будет логическим следствием формулы F тогда и
- 57. Логическое следствие Определение. Формула B называется логическим следствием формул A1, A2, …,An если для всех наборов
- 58. Аксиомы исчисления высказываний Для полного набора логических связок: импликация, отрицание, конъюнкция и дизъюнкция система содержит десять
- 59. Определение исчисления высказываний, как и любой формальной системы, следует начинать с задания множества аксиом и правил
- 60. Аксиомы исчисления высказываний Множество формул, удовлетворяющих условиям тождественной истинности, бесконечно. Однако в качестве аксиом всегда выбирают
- 61. Аксиомы исчисления высказываний: А1. F1→(F2→F1); А2. (F1→F2)→((F2→F3))→(F1→F3)); А3. (F1∧ F2)→F1; А4. (F1∧ F2)→F2; А5. F1→(F2→(F1∧F2)); А6.
- 62. Связь между алгеброй высказываний и исчислением высказываний. Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний.
- 63. Теорема 1. Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной в алгебре высказываний. Формулировка этой
- 65. Скачать презентацию