Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул



страница2/3
Дата02.01.2013
Размер0.68 Mb.
ТипКонтрольная работа
1   2   3

Домашняя работа по исчислению

  • высказываний и логике предикатов

  • При решении задач по исчислению высказываний (ИВ) можно пользоваться одной из двух систем аксиом ИВ (двумя сразу нельзя):


    А1. А А) 1. А А)

    А2. (А С)) ((А В) С)) 2. (А В) ((А С)) С))

    А3. ( В А) (( В А) В) 3. А В А

    4. А В В

    5. А В))

    6. А В)

    7. В В)

    8. (А С) ((В С) ((А В) С))

    9. (А В) ((А В) А)

    10. А А

    При использовании системы аксиом вывод будет короче. Вывод в ИВ – это последовательность формул, где каждая формула или аксиома, или теорема, или гипотеза, или получена по правилу вывода. Правило вывода m.p.: Если в выводе есть две формулы вида А В и А, то после них в выводе можно писать формулу В. Считается, что формула В получена по правилу m.p. из формул А и А В. Правило записывается так: А, А В
    1. или А, А В В. В


    Выводом формулы А считается вывод, в котором формула А является последней. Если в выводе формулы А отсутствуют гипотезы, то формула А называется теоремой ИВ. Все аксиомы являются как бы схемами аксиом, в них вместо формул А, В и С можно корректно подставить любые формулы. Если формула А заменяется другой формулой, то сразу во всей аксиоме. В выводе можно применять теорему о дедукции ИВ: если Г, А В, то Г А В и два её следствия: 1. А В, В С А С. Построим вывод формулы А С. 1) А В – гипотеза № 1; 2) В С – гипотеза № 2; 3) А – гипотеза № 3; 4) В получена по m.p. из первого и третьего шагов (из 1) и 3) ); 5) С получена по m.p. из 2) и 4). Вывод формулы С имеет длину пять. В итоге получили: А В, В С, А С. Применяем теорему о дедукции ИВ, переносим формулу А вправо и получаем: А В, В С А С. Следствие 2: А С), В А С. Вывод длиной 5: А С); В; А; В С; С. Четвёртый шаг получен по m.p.
    из первого и третьего шагов, а пятый – из второго и четвёртого. Получили А С), В, А С, применяя дедукцию, получим второе следствие. Следствия можно считать ещё двумя правилами вывода. В правилах вывода тоже, как и в аксиомах, можно корректно одновременно во всём правиле вывода одну формулу заменять другой. Правило m.p. может быть записано и так: , .

    При выводе можно использовать 7 теорем ИВ: Т1. А А.

    Т2. А А. Т3. А В). Т4. ( В А) В). Т5. (А В) ( В А). Т6. А ( В В)). Т7. (А В) (( А В) В). В теоремах ИВ, в том числе и в теореме о дедукции и её следствиях, формулы С, А и В так же могут быть корректно заменены другими.

    Для примера получим ещё одно правило вывода: А, В А В. В пятую теорему вместо формулы А поставим формулу В, а вместо В поставим А и получим: (В А) ( А В). Теоремы и аксиомы можно вставлять в любое место вывода. Теперь вывод формулы В длиной 5: А; В А; (В А) ( А В); А В; В. Четвёртый шаг вывода получен по m.p. из второго и третьего шагов, а пятый – из первого и четвёртого. Все три вновь полученные правила вывода можно применять, как и правило m.p., наряду с теоремой о дедукции.

    Во втором задании по логике предикатов надо написать всё, что требуется в задании с использованием логики предикатов. Никакой дополнительной информации для выполнения задания не требуется, всё есть в самом задании. Например: на множестве натуральных чисел N имеется два трёхместных предиката: S (x,y,z)=1 x+y=z, P (x,y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу с одной свободной переменной x, истинную тогда и только тогда, когда x делится на три. Ответ: F(x)=( z)( S (z,z,y) S (z,y,x)). z+z=y и y+z=x, значит x=3 z. А можно и так: F(x)=( z) P (3,z,x) – это тоже правильно.

    Теорема Ферма утверждает, что для любого целого n>2 не существует натуральных чисел x, y и z, удовлетворяющих равенству: x +y =z .Этому равенству поставим в соответствие предикат R (x,y,z,n) на множестве натуральных чисел, истинный тогда и только тогда, когда равенство выполняется. (n>2) запишем, используя предикаты предыдущего примера: ( z) S (3,z,n). Теорему Ферма можно записать так: (( z) S (3,z,n)) R (x,y,z,n).

    Докажем теорему ИВ А A, т.е. выведем А A из пустой системы гипотез ( А A), или, другими словами только из аксиом и теорем ИВ. 1) A ( A A) ( 7); 2) A ( A A) ( 6); 3) (A ( A A)) (( A ( A A)) ( А A)) (Т7); 4) ( A ( A A)) ( А A) (m.p. 1) и 3)); 5)

    А A (m.p. 2) и 4)).
  • 1   2   3

    Похожие:

    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconНормальные формы формул логики предикатов
    При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной...
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon5. 11. Как упростить логическую формулу?
    Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для...
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconКонтрольная работа «Электрический ток»
    По какой из приведенных ниже формул можно рассчитать тепловую мощность тока на внешнем участке цепи?
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconРабота с текстовым процессором ms word: набор формул, создание списка иллюстраций, перекрестных ссылок, элементов автозамены и автотекста
    Создайте новый документ, введите текст "Создание формул" и сохраните документ в своей папке под именем Формула doc
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconПодбор формул по графику. Линия тренда Подбор формул со многими неизвестными Расчет стоимости недвижимости Оценка эффективности рекламы Подбор формул по графику. Линия тренда
    По ним с определенной мерой близости пытаются восстановить эмпирическую формулу (уравнение), которая может быть использована для...
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconКонтрольная работа по теме «Электростатика»
    По какой из приведенных ниже формул можно рассчитать в си модуль напряженности электростатического поля точечного заряда q, находящегося...
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconВопросы вступительного экзамена в аспирантуру по специальности 01. 01. 06 – математическая логика, алгебра и теория чисел
    Истинностные значения формул, равносильность, равносильные преобразования формул. Представление истинностных функций формулами
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon§ Определение доказуемой (выводимой) формулы
    Следующим этапом в построении исчисления высказываний является выделение класса доказуемых (выводимых) формул
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon«Технология графических материалов» 3 курс 6 семестр (озо) Контрольная работа
    Контрольная работа проходит в форме теста с использованием компьютерных технологий. В форме слайд-шоу студентам предлагается некоторое...
    Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconЛогические операции над предикатами
    Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов...
    Разместите кнопку на своём сайте:
    ru.convdocs.org


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