Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга



Скачать 165.68 Kb.
страница1/5
Дата08.10.2012
Размер165.68 Kb.
ТипЛекция
  1   2   3   4   5
Лекция 9

Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга.
I Формальные системы (ФС)



A – алфавит имён

З – алфавит специальных разделительных знаков

ППФ – правильно построенные формулы из имён и знаков

А ППФ – формулы, которые называются аксиомами

ПВ – правила вывода на множестве ППФ вида «если , то »

Исчисление , такое что I конструктивно порождается из множества аксиом применением ПВ.

Пример 1. Формальные грамматики. , где A – терминальный алфавит; V – вспомогательный алфавит; Р – правила вывода, вида , где (все слова из объединённого алфавита); S – начальный вспомогательный символ (начало порождения) суть аксиома.

Грамматика G порождает (исчисляет) язык , который является множеством слов, выделенных для целей синтаксического описания моделей некоторых объектов (например, языка программирования ALGOL).
II. Формальная модель высказываний (язык высказываний)

  1. A – алфавит имён =.

  2. Z – алфавит знаков ={, &, , V, , , другие знаки логических операций, – скобки }.

  3. ППФ суть скобочные формулы из A и Z, построенные по определённым правилам, например – есть ППФ, а формула не является ППФ. Буквами A, B, C и т.д. обозначаются сложные ППФ.

  4. Семантика ППФ.

    1. Каждое суть атомарное высказывание. Например, р – «студент спит», q – «слоны живут в Африке»

    2. Каждое ППФ образует сложное высказывание, где знаком придаётся смысл логических связок между высказываниями.


– смысл: если А то В (из А следует В).

– смысл: А и В.

– смысл: А или В, но не оба вместе (разделённое или).

– смысл: А или В.

– смысл: А тождественно (эквивалентно) В.

– смысл: не А, другое обозначение –

Пример: р – студент спит, q – время идёт, r – лекция скучная.

Студент спит, а время идёт ~.

Студент спит, если лекция скучная – .

  1. Интерпретация ППФ.

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

    2. Каждой ППФ приписывается значение в зависимости от интерпретации связок как знаков операций. Интерпретация связок соответствует таблицам истинности ФАЛ.

Например:

А В


АВ

л л

л и

и л

и и

и

и

л

и


  1. Если при некоторой интерпретации ППФ истинна, то она называется выполнимой на данной интерпретации.

  2. Если ППФ выполнима (истинна) на всех наборах, то она называется тождественно истинной, либо тавтологией, либо общезначимой.

  1. Другие интерпретации ППФ.

а) Многозначные логики. Например, каждое атомарное высказывание из ППФ и сама ППФ получают значение из множестватроичная логика.

б) Правдоподобная логика. Введена Д. Пойа в книге «Математика и правдоподобные рассуждения». ППФ принимают значения из множества и интерпретируется как мера правдоподобности высказывания. Д. Пойа ввёл правила для вычисления правдоподобности сложенных высказываний по правдоподобности его составляющих.
III. Специальный вид высказываний – рассуждения или

умозаключения.

  1   2   3   4   5

Похожие:

Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЛекция 2 Доказательство тавтологий Алгоритм Квайна
Этот алгоритм состоит в том, что переменным высказываниям, упорядоченным в набор, последовательно придаются значения и и л и анализируются...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconПонятие алгоритма
Ом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЗадача на быстродействие. Алгоритм ее решения. Классическое вариационное исчисление. Уравнение Эйлера. Задачи
Алгоритм поиска решения задачи оптимизации "в среднем". Нахождение функции /достижимости. Теорема Ляпунова, лемма Каратеодори
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЛекция 3 Построение минимальных днф с помощью карт Карно. Алгоритм Квайна- мак-Клоски 1 Минимальные днф
Я строится по таблице булевой функции, зачастую оказывается весьма сложной, т е она содержит достаточно много элементарных конъюнкций...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга icon«Циклические алгоритмы. Алгоритм Евклида»
Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (нод) двух целых неотрицательных чисел
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconВолновой алгоритм (Алгоритм Ли)
Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу (путь) между двумя элементами...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЛекция 4 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЛекция 3 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconЛекция 33. Особенности моделирования на базе q-схем. Детерминированный моделирующий алгоритм. Синхронный моделирующий алгоритм. Асинхронный моделирующий алгоритм. Возможности модификации моделирующих алгоритмов q-схемы
Вм позволяют достаточно эффективно провести моделирование различных систем, формализуемых в виде q-схем, используя либо языки общего...
Лекция 9 Исчисление высказываний Проверка выводимости правильных умозаключений. Алгоритм Квайна. Правило резолюций. Алгоритм Вонга iconАлгоритм (Делай раз, делай два)
Обеспечить понимание учащимися терминов «информатика», «информация», «компьютер», «алгоритм», «команда алгоритма». Систематизировать...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org