95622

ПРОПОЗИЦИОНАЛЬНОЕ ИСЧИСЛЕНИЕ И ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

Лекция

Экономическая теория и математическое моделирование

Программирование в значительной мере связано с доказуемостью и с выводимостью. Мы должны иметь возможность понимать поведение программы во время ее выполнения. Для этого существует такая наука выводимости, как логика.

Русский

2015-09-25

30.83 KB

0 чел.

5

Лекция 4.   ПРОПОЗИЦИОНАЛЬНОЕ ИСЧИСЛЕНИЕ И

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

Программирование в значительной мере связано с доказуемостью и  с выводимостью. Мы должны иметь возможность понимать поведение программы во время ее выполнения. Для этого существует такая наука выводимости, как  логика.

Опр.: ЛОГИКА – это механизм, стоящий за способностью человека делать выводы, доказывать утверждения в соответствии с правилами логики. Логика – основа разработки программного обеспечения. Разработка ПО  требует доказуемости, а точные выводы требуют законов логики. (При изучении контрактов используются условия в форме булевских выражений).

Законы логики

Логика нужна  для понимания той части выводимости, которая базируется на условиях.

Рассмотрим булеву алгебру в форме пропозиционального исчисления (propositions - высказывания), которое имеет дело с базисными высказываниями, включающими специфические переменные. Далее расширим обсуждение до логики предикатов, которая позволяет выражать свойства произвольного множества значений.

Булевские значения, переменные, операции, выражения.

Булевские константы или истинностные значения – это 1,0 (true,false). Булевские переменные используем для того, чтобы выразить свойство, которое может иметь в качестве своего значения истину или ложь (1,0). Булевские операции  and,or,not, implies, = , которые задают правила вычисления значения результирующего выражения по заданным значениям ее операндов. Отдельно следует иметь ввиду операцию xor – «исключающее или».

Математические символы – аналоги булевским операциям:

not   –       ┐  или  ~

or     –       v  или  |

and   –      ^  или  &

 =     -       или  =

implies -      =>

xor   – исключающее или

                    Задание: Для всех операций составить Таблицу истинности.

Опр.: Истинностным присваиванием (assigment) для множества переменных  называется индивидуальный выбор значений 1 или 0 для каждой из переменных (например в каждой строке таблицы истинности).

Для выражения из n переменных существует 2n  истинностных присваиваний, а значит, 2n  строк в таблице истинности.

Опр.: ТАВТОЛОГИЯ – булевское выражение, принимающее значение 1 для всех возможных истинностных присваиваний переменным этого выражения.

Например, выражения:

              A or (not A),     not (A and (not A)),     (A and B) or ((not A) or (not B))

Опр.: ПРОТИВОРЕЧИЕ -  булевское выражение, принимающее значение 0 для каждого  истинностного присваивания его переменным.

Например,  A and (not A)

Опр.: Выражение, имеющее значение 1 хотя бы для одного истинностного присваивания, называется ВЫПОЛНИМЫМ.

Отсюда сделаем вывод, любая тавтология выполнима и никакое противоречие не является выполнимым.

Эквивалентность  ( = )

Равенство подразумевает эквивалентность.   Эквивалентность определяет общие правила для доказательства или опровержения тавтологий, противоречивости и выполнимости.

Выражение A = B имеет значение 1, если и только если переменные А и В имеют  одинаковые значения.

Теорема: «Подстановка»

 Для любых булевских выражений V1,V2 и V3, если V1 =  V2  является тавтологией и  V~  -  выражение, которое получено из V3 путем замены каждого вхождения V1 на V2 , то

                    V3  = V~    - это тавтология.                                                 (c.118).

Например,    (A and (not (not B))) = (A and B) – выражение есть тавтология.      (*)

Для доказательства сперва докажем, что для любого выражения  V следующие общие свойства являются тавтологиями:

 T1     not (not V)  = V

 T2     V = V   – эта тавтология  следует из рефлексивности тавтологии операции =.

Доказательство: Доказать утверждение Т1 просто через таблицу истинности. Далее, применим Т1 к выражению В в (*) используя теорему о подстановке, путем замены    not(not B)  на В,  в левой части выражения (*). После этого применим Т2 к  A and B и получим желаемый результат.

Можно использовать два символа  /= , означающий «не равно», «не эквивалентно», что эквивалентно выражению  not (A = B).

 Ассоциации между операциями  or  и  and

А1: Отрицание одной из операций эквивалентно применению другой операции над отрицаниями операндов.

А2:  Каждая из этих операций дистрибутивна (distribute - распределять) по отношению к другой операции.

                Теорема: « Дистрибутивность булевских операций »

Следующие два свойства являются тавтологиями:

                         (A and ( B or C)) = ((A and B) or (A and C))

      (A or (B and C)) = ((A or B) and (A or C))

Доказательство через таблицу истинности. В математике – дистрибутивность умножения по отношению к операции сложения – есть:

                         A * (B+C)  эквивалентно  (A * B) + (A * C).

 Приоритеты операций (слева - направо) – not, =, and, or, implies

Ассоциативность операций – это свойство, которое  упрощает нотацию написания булевских выражений.

Операции and и or – ассоциативны, что выражается следующими тавтологиями:

                      (A and (B and C)) = (( A and B) and C)

                      (A or ( B or C))  =  ((A or B) or C),

что позволяет писать выражения в форме:

A and B and C   или   A or B or C.

ИМПЛИКАЦИЯ

Импликация (implies - влечет) – базисная операция.

Опр.:  Значение выражения  А  implies  В   для любых булевских значений переменных А и В  является значением   (not A) or B.

A       B      A implies B

1        1            1

1        0            0

0        1            1

0        0            1

где А – это посылка (antecedent),  В –  следствие, заключение (consequent).

Импликация  имеет  истину  когда: посылка имеет 0, либо когда заключение имеет 1.

Теорема: «Импликация и вывод»

  1.  Если истинностное присваивание удовлетворяет как А, так и A implies B, то оно удовлетворяет и В.
  2.  Если оба А и A implies B являются тавтологиями, В – также тавтология.

В логике операция  implies  не  ассоциируется  с  причинностью!!!,  эта операция просто устанавливает, что когда одно свойство является истинным, таковым должно быть и другое свойство. Другими словами, если посылка верна, то это же верно и для заключения. Когда А ложно, то А implies В  истинно, НЕЗАВИСИМО от значения  В.

В логике импликация не ассоциируется с причинностью, а в практике - да.

Таким образом, базисными элементами исчисления высказываний (пропозициональным исчислением) являются высказывания (propositions), каждое устанавливающее единственное свойство Р, которое может принимать только два значения – 1 и 0. Например, «Число n - положительно», «Я - аким Алматы», «Сегодня ночью будет полная луна».

Единственность свойства Р в приведенных примерах означает, что Р характеризует ЕДИНСТВЕННЫЙ объект – это число, я, текущая ночь или конечное множество явно перечисленных объектов, как например в высказывании «Я – не аким, и сегодня ночью нет полной луны».

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

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

В исчислении предикатов для этого вводятся выражения с кванторами объектов, позволяя ссылаться только на само множество.

Квантор существования -  exists  или  , в математической нотации    устанавливает что, по крайней мере, хотя бы один член множества обладает свойством Р. Квантор всеобщности – for_all или в математической нотации  , чтобы установить, что все без исключения члены множества обладают свойством Р.

Когда требуются булевские операции для произвольного числа операндов, exists обобщает операцию or, а  for_all  - обобщает операцию and.

Пусть  Х = {3,7,9,11,13,15}.   Пусть для любого целого n  свойство n.is_odd означает, что n - нечетно; свойство   n.is_even  - n - четно и   n.is_primen - простое число. Тогда

 n : X | n.is_odd   означает, что по крайней мере ОДИН из членов Х является нечетным. Для нашего множества значение выражения – есть истинна (true).

 n : X | n.is_evenозначает, что по крайней мере хотя бы один из Х является четным. Для нашего множества  выражение  имеет значение – ложь (false).  

Мы привели примеры того, как можно доказать или опровергнуть выражение с квантором существования     s: some_set | s.some_property (property - свойство).

Недостаточно найти один элемент, который не удовлетворяет заданному свойству, проверке должны подлежать  все члены множества.

Квантор всеобщности - , его значение равно 1, если каждый элемент множества, если он существует, удовлетворяет свойству Р.  Если хотя бы один элемент не удовлетворяет свойству Р, то  нет необходимости в анализе всех элементов множества.

Следующие два свойства обобщают закон Де Моргана:

  1.      not ( s: E | P)  =  s : E| not P- это следует из определения
  2.      not ( s: E| P)  =  s: E not P    -  следует из применения (1) к not P и отрицания обеих сторон.

Рассмотрим случай пустых множеств

 s : set | s.P – истинно, если и только  если некоторый член множества set удовлетворяет свойству Р. Если множество set пусто, и тем самым нет члена удовлетворяющего свойству Р, то значение выражения, независимо от Р, всегда ложь (0).

Другой способ выражения квантора существования для пустого множества, когда n = 0:

A1 or A2 or A3 …. or An дизьюнкция ложна, что следует из определения операции or: A or B истинно,  если и только  если  по меньшей мере один из элементов А или В истинен. Но в пустом множестве нет члена удовлетворяющего свойству Р, поэтому значение выражения независимо от свойства Р всегда есть ложь.

set | s.P ложно, если и только если некоторые члены множества set не удовлетворяют свойству Р. Если множество set пусто, то и нет члена, который бы играл роль «контрпримера», поэтому значение выражения всегда истинно.

Другой способ выражения квантора всеобщности – A1  and A2  … and An  - истинно, так как  А and B ложно, если и только если по крайней мере один из элементов А или В ложен.

Рассмотрим способ выражения квантора всеобщности через импликацию. Можно понимать   set | s.P    как следующую импликацию:

«s is a member of set»  implies s.P,  

так как посылка ложна, для каждого возможного s, что дает истинность импликации. Так как множество set пусто, то посылка ложна для каждого возможного s, поэтому импликация истинна.


 

А также другие работы, которые могут Вас заинтересовать

80178. Перевод энергоблока из состояния «Реактор критичен» в состояние «Работа на мощности» 111.5 KB
  Перевод энергоблока из состояния Реактор критичен в состояние Работа на мощности План лекции. Увеличение мощности реактора до 5 Nном. Увеличение мощности реактора до 2039 Nном. Увеличение мощности реактора до 7580 Nном.
80179. Эксплуатация энергоблока в состоянии «Работа на мощности» 158.5 KB
  В работе находятся вспомогательные системы обеспечивающие подачу масла запирающей воды промконтура и воды VB на соответствующие ГЦН. Работоспособны системы отвода генерируемого пара по второму контуру: все четыре БРУА; все четыре БРУК при наличии вакуума в конденсаторе; хотя бы один БРУСН и коллектор собственных нужд. TQ13 2333 Все три канала системы аварийного ввода бора TQ132333 работоспособны и готовы к работе. TQ14 2434 Все три канала системы аварийного впрыска бора высокого давления TQ142434 работоспособны и...
80180. Эксплуатация энергоблока при снижении и повышении нагрузки генератора 147.5 KB
  Организация выставления уставок по нейтронной мощности при изменении мощности энергоблока. В результате изучения материала лекции студенты должны: а знать: действия оперативного персонала для снижения мощности генератора; действия оперативного персонала для повышения мощности генератора; б уметь выполнять действия для изменения мощности энергоблока; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при изменении нагрузки генератора. После получения распоряжения от НСС на снижение мощности ЭБ до нового уровня НСБ...
80181. Эксплуатация энергоблока с неполным числом петель первого контура 78 KB
  Подготовка вспомогательных систем ГЦН к работе. В результате изучения материала лекции студенты должны: а знать: действия оперативного персонала при плановом отключении ГЦН; действия оперативного персонала при плановом запуске ГЦН; б уметь выполнять действия для останова и пуска ГЦН; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при работе с различным числом включенных ГЦН. Ситуации требующие отключения одного или двух ГЦН в процессе эксплуатации являются довольно частыми. Реакторная установка допускает...
80182. Перевод энергоблока из состояния «Работа на мощности» в состояние «Горячий останов» 102.5 KB
  Останов турбины со срывом вакуума. В результате изучения материала лекции студенты должны: а знать: возможные способы уменьшения мощности реакторной установки; действия оператора при останове турбины; б уметь выполнять уменьшение мощности реактора и турбогенератора; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при снижении его мощности. В процессе разгрузки РУ контролируется: синхронность движения ОР СУЗ рабочей группы; снижение номинального уровня в КД по мере снижения мощности реактора и средней...
80183. Перевод энергоблока из состояния «Горячий останов» в состояние «Холодный останов» 143.5 KB
  Расхолаживание 1го контура. Расхолаживание 1го контура системой TQ122232 . Окончательное расхолаживание 1го контура и перевод РУ в состояние Холодный останов. В результате изучения материала лекции студенты должны: а знать: возможные способы расхолаживания реакторной установки; действия оператора при расхолаживании реакторной установки; б уметь выполнять расхолаживание реакторной установки; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при расхолаживании 1го контура.
80184. Перевод энергоблока в состояние «Останов для ремонта» и «Останов для перегрузки» 110 KB
  Дренирование первого контура и консервация ПГ. В результате изучения материала лекции студенты должны: а знать: возможные способы консервации оборудования ЭБ; мероприятия проводимые при подготовке ЭБ к ремонту; б уметь выполнять дренирование 1го контура; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при его переводе в состояние Останов для ремонта. Дренирование первого контура и консервация ПГ Подготовка к дренированию первого контура . Концентрация НзВОз в теплоносителе первого контура доведена до...
80185. Нарушения нормальной эксплуатации, обусловленные несанкционированным изменением реактивности 123.5 KB
  Несанкционированное движение вверх регулирующей группы ОР СУЗ. Нештатное положение ОР СУЗ и действия персонала в случае застревания ОР СУЗ при срабатывании аварийной защиты. Данное нарушение может обусловливаться разными причинами: например обесточиванием УКТС АЗ и панелей аварийной защиты потерей питания панелей щита СУЗ ложными сигналами в цепях аварийных защит а также ошибочными действиями персонала не связанными с необходимостью аварийного останова блока путем принудительного срабатывания аварийной защиты. Падение ОР СУЗ .
80186. Нарушения нормальной эксплуатации, обусловленные снижением расхода теплоносителя через реактор 92 KB
  Отключение одного ГЦН из 3х или 4х работающих. Отключение 2х ГЦН из 4х работающих. Отключение одного ГЦН из четырех работающих с наложением отказа в работе РОМ. В результате изучения материала лекции студенты должны: а знать: возможные причины отключения ГЦН; действия персонала при подобных нарушениях нормальной эксплуатации; б уметь восстанавливать нормальную работу РУ и ТУ в подобных ситуациях; в быть ознакомленными с физическими основами процессов протекающих на ЭБ при отключениях ГЦН.