Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n!




Скачать 249.94 Kb.
НазваниеPn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n!
страница3/3
Дата публикации01.04.2013
Размер249.94 Kb.
ТипДокументы
vbibl.ru > Математика > Документы
1   2   3
^

Доказательство (от противного)


Предположим, что B не является тавтологией, тогда существуют значения букв, на которых B является ложным, тогда: (истина  ложь) – истина, потому что по условию (A  B) – тавтология, это противоречит определению импликации, следовательно =B – тавтология.

2. Подстановка в тавтологию приводит к тавтологии. Предположим: =A, в нее входят пропозициональные буквы a1, a2, … an; заменим ai на Ai (ПФ), i=1..n. В результате этой замены мы получим пропозициональную формулу B, откуда =B.

Доказательство


Зададим буквам, входящим в B, некоторые значения, тогда формулы Ai примут некоторые значения, зададим эти значения буквам ai, входящим в формулу A, тогда значение формулы A совпадает со значением формулы B, поскольку A является всегда истинным, то и B примет значение “истина”, следовательно B – всегда “истина” или B – тавтология.

3. Предположим A – ПФ, а – ПФ, входящая в A, заменим a на b в формуле A хотя бы один раз. В результате этой замены мы получили ПФ B, тогда:

= (ab)  (AB)

Доказательство

A B

ab
AB

0 0

0 1

1 0

1 1

1

0

0

1

1

0

0

1

Если a и b одинаковы, то одинаковы и A и B.

^ Приоритеты логических связок

младший  <  <  < & <  старший

Принцип двойственности

Предположим, что A – ПФ, содержащая только операции &, , ; A’ получается заменой в A  на & и & на , тогда:

  1. =A  =A’

  2. если =A  B, то =B’  A’

  1. если =A  B, то =A’  =B’

A* (ПФ) получается из формы A, если произведем замены:

  &;

&  ;

a  a;

a  a.

A* – негатив для формулы A

  1. = (A  A*)

^ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

Знак “:” = “такой, что”

M – произвольное множество

B = {0,1}

Предикат – функция P(x1, x2, x3, … xn): Mn  B, MM…M=Mn, xiM

M – предметная область предиката

xi – предикатные переменные

B – область значений предиката

^ Связь отношений и предикатов

R  Mn

R = {(a1, a2, … an), aiM}


Обратное отношение

Пусть есть высказывание



Связь между предикатами и функциями:

f: Mn  M

(n+1)-местный предикат

Обратный переход от предиката к функции возможен не всегда потому, что могут быть предикаты, в которых:

P (a1, a2, a3) = Истина,

P (a1, a2, a3) = Истина.

Из предикатов можно образовывать логически формулы:

P1(x1, x2)  (P2(x3, x4) & P1(x2, x3))

Формулу можно рассматривать как составной предикат:

Q(x1, x2, x3, x4)
^

Примеры предикатов


  1. P(x, y) = x  y

  2. P(x) = x > 5

  3. do f(x, y, z) while ((x = y) & (i < 100))



Исчисление предикатов применяется при доказательстве правильности программы.

Кванторы

Введенных логических операций недостаточно для формализации всего множества используемых высказываний, поэтому множество этих связок расширяется за счет введения кванторов.

 – “для всех x из M P(x) – истина” – квантор общности

x P(x) или xM P(x)

 – “существует x из M, для которого P(x) – истина” – квантор существования

x P(x) Операция добавления квантора к предикату называется навешиванием квантора на переменную или связыванием переменной (квантификация). Переменная x, на которую повешен квантор, называется связанной, несвязанные переменные называются свободными. Свободная переменная – это обычная переменная, она может принимать любые значения. Навешивать кванторы можно на предикаты и вообще на любые логические выражения. Выражения, на которые навешиваются кванторы, называются областью действия квантора. Все вхождения переменных, указанных в кванторе, являются в выражении связанными. Навешивание квантора на предикат уменьшает количество свободных переменных в нем. x P(x, y, z) = Q (y, z)

^ Истинные формулы и эквивалентные соотношения в исчислении высказываний

F – формула, которая может содержать предикаты, логические связки, кванторы.

1) формула F называется выполнимой в заданной области M, если существует такая подстановка логических констант в переменные, при которой F становится истинным высказыванием;

2) формула F называется выполнимой, если существует область M, в которой F выполнимо;

3) если формула F выполнима во множестве M при любых подстановках констант, она называется тождественно истинной во множестве M;

4) формула F тождественно истинная для любого множества M называется просто тождественно истинной или общезначимой, или тавтологией;

5) если формула F невыполнима в множестве M, то она называется тождественно ложной во множестве M;

6) если формула F невыполнима для любых M, она называется просто тождественно ложной или противоречием.

x (P(x)  P(x)) – тождественно истинна

x (P(x) & P(x)) – тождественно ложна

Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения, в частности все тождественно истинные (ложные) формулы являются эквивалентными. Если формулы F1 и F2 – эквивалентны, то = (F1  F2). В математической логике существуют две проблемы при исследовании истинности формул.

- определение порождающей процедуры для множества истинных формул;

- проверка формулы на истинность – проблема построения разрешающей процедуры для множества истинных формул.

Для этого – построение таблицы истинности. Порождающую процедуру можно организовать так: строим последовательно все формулы, проверяем их на тождественную истинность, и те формулы, которые тождественно истинны, включаем в множество тождественно истинных формул. В логике предикатов предикатные переменные имеют в общем случае бесконечные области определения, поэтому прямой перебор в общем случае невозможен, и нужно применять методы доказательства.

Формулы преобразования

  1. ( x P(x))  x (P(x))

  2. ( x P(x))  x (P(x))

Вынесение квантора:

  1. x (P1(x) & P2(x))  x P1(x) & x P2(x)

  2. x (P1(x)  P2(x))  x P1(x)  x P2(x)

  3. x (P1(x)  P2(x))  x (P1(x)  x P2(x))

  4. x (P1(x) & P2(x))  x P1(x) & x P2(x)

  5. x y P(x, y)  y x P(x, y)

  6. x y P(x, y)  y x P(x, y)

x y P(x, y)  y x P(x, y)

Предваренные нормальные формы

Формула представлена в ПНФ (предваренная нормальная форма), если она имеет следующий вид (K – квантор):

K1x1 K2x2 K3x3 … Knxn M

M – матрица

до M – кванторное начало (префикс)

Если все кванторы существования предшествуют всем кванторам общности, то такая форма называется нормальная форма Сколема.

Существует формальный алгоритм построения предваренных нормальных форм. Цель алгоритма вынесение квантора влево.

Шаг 1:

Исключение связок эквивалентности и импликации, заменой их на , , &.

P  Q  P & Q  P & Q

P  Q  P  Q

Шаг 2:

Вносят отрицание внутрь формул с применением законов:

 (P)  P

 (P  Q)  P & Q

 (P & Q)  P  Q

– законы де Моргана

 ( x P(x))  x (P(x))

 ( x P(x))  x (P(x))

Шаг 3:

Переименовываем связанные переменные, если это необходимо (формулы 5 и 6)

Шаг 4:

Используем оставшиеся формулы для вынесения кванторов в самое начало формулы
1   2   3

Похожие:

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconСварка с помощью нагревательных элементов
По ошибке сваркой называют способ холодного соединения или соединения с набуханием пластика, который не подпадает под данное понятие,...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconФедеральное агентство железнодорожного транспорта
Так же с помощью наружной рекламы можно выработать у потенциального потребителя позитивное (или не очень) отношение к бренду или...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconПермский государственный технический университет
Выполните задания 1-4 с помощью двойного интеграла, задания 5-7 с помощью тройного интеграла, задания 8-11 с помощью криволинейных...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconО программе iTunes
Создавайте плейлисты на любой случай жизни. Записывайте плейлисты на компакт-диск и воспроизводите их на домашней или автомобильной...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconФорматирование текста
Текстовый курсор и символ конца текста. Текстовый курсор передвигается с помощью клавиш управления курсором или с помощью щелчка...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconУрока, дата Главная тема Важнейшие подтемы
Умение работать с историческими источниками- работа и анализ текста с помощью маркировки ( статьи о новых научных открытиях или просмотр...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconЙогическая садхана под редакцией уттара йоги
Волю, с помощью Воли воспитайте знание, с помощью знания очистите сердце, установите контроль над энергиями тела и успокойте ум....

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconШаг Утечка информации
Раскрутка нового бренда с помощью рекламы и с помощью пиара совсем не одно и то же. Если вы хотите раскрутить бренд с помощью пиара,...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconУслуги междугородной и международной телефонной связи Orange Business...
Автоматическая телефонная связь позволяет абоненту без предварительного заказа, в любой момент времени установить соединение по телефону...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconМногие дети проходят период между двумя и четырьмя годами, когда...
Дети, которые, подрастая, не научатся подавлять свою агрессивность и общаться с окружающими с помощью устной речи, часто превращаются...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница