Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Кванторы

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Пусть P(x1,x2...xn) — n-местный предикат, определенный на M. Зафиксируем xi=a. Определим (n-1)-местный предикат Q(x1,x2...xk-1,xk+1,xn) следующим образом: Q(x1,x2...xk-1,xk+1,xn)=P(x1,x2...xk-1,xk+1,a,xn). Говорят, что предикат Q(x1,x2...xk-1,xk+1,xn) получен из предиката P(x1,x2...xn) фиксацией значения i-й переменной: xi=a.
     Определение 1. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∀xP(x) (читается «для любого х Р(х)»), которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании ∀xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.
     Определение 2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∃xP(x) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании ∃xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.
     Замечание 1. Обозначения ∀ и ∃ для кванторов — это перевернутые латинские буквы А и Е соответственно, которые являются первыми буквами в английских словах All — все, Exist - существовать.
     Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами (или предикатами любой местности).
     Пусть P(x11,x2...xn) — n-местный предикат, определенный на M. Зафиксируем в нем значения переменных x1,x2...xk-1,xk+1,xn. На полученный одноместный предикат Q(xk) навесим квантор всеобщности (существования), получим высказывание. Тем самым фиксированному набору значений переменных x1,x2...xk-1,xk+1,xn с помощью квантора всеобщности (существования) поставлено в соответствие высказывание. Говорят, что этот (n-1)-местный предикат переменных x1,x2...xk-1,xk+1,xn получен из исходного предиката P(x11,x2...xn) навешиванием квантора всеобщности (существования) по k-й переменной. Этот предикат обозначают: ∀xkP(x1,x2...xn) (∃xkP(x1,x2...xn)). Об k-й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования).
     Пример 1. Пусть D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двухместный предикат. Навесим последовательно на его переменные кванторы. Ясно, что:
     1) ∀x1∀x2D(x1,x2)=0
     2) ∀x2∀x1D(x1,x2)=0
     3) ∃x1∃x2D(x1,x2)=1
     4) ∃x2∃x1D(x1,x2)=1
     5) ∀x1∃x2D(x1,x2)=1
     6) ∃x2∀x1D(x1,x2)=1
     7) ∃x1∀x2D(x1,x2)=0
     8) ∀x1∃x2D(x1,x2)=1
     Таким образом (сравнением 7 и 8 в последнем примере) мы доказали теорему.
     Обычно, связки и кванторы упорядочиваются по приоритету следующим образом ¬, ∀, ∃, &, v, →, ∼.
     Теорема 1. Разноименные кванторы, вообще говоря, не коммутируют.
     Теорема 2. (основные равносильности, содержащие кванторы).
     Имеют место следующие равносильности:
     1. Законы де Моргана
         ¬(∀xP(x))=∃x¬(P(x))
         ¬(∃xP(x))=∀x¬(P(x))
     2. Коммутативность
         ∀x∀yP(x,y)=∀y∀xP(x,y)
         ∃x∃yP(x,y)=∃y∃xP(x,y)
     3. Дистрибутивность
         ∀x(P(x)&Q(x))=∀xP(x)&∀xQ(x)
         ∃x(P(x)&Q(x))=∃xP(x)&∃xQ(x)
     4. Ограничение действия кванторов
         ∀x(P(x)vQ(y))=∀xP(x)vQ(y)
         ∃x(P(x)&Q(y))=∃xP(x)&Q(y)
     5. Для любого двухместного предиката
         ∃y∀xP(x,y)→∀x∃yP(x,y)=1

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru