Предикат это в программировании: Жаргон функционального программирования / Хабр

Содержание

Что значит предикат — Значения слов

Примеры употребления слова предикат в литературе.

Человеческие они или божественные, как говорил Штирнер, предикаты всегда одни и те же — принадлежат ли они аналитически божественному бытию или же синтетически связаны с человеческой формой.

В том или ином ограниченном виде они часто встречаются в литературе: предикаты и синтагмы в классической лингвистике, управление и примыкание, актантное и атрибутивное отношения, отношения в ПРОЛОГ-системах обработки естественного языка.

Следовательно, Лейбниц очень хорошо понимал приоритетность и изначальность события по отношению к предикату.

В этом случае между элементами возникает отношение предикации, подразумевающее их качественное различие, причем один из элементов интерпретируется как логический субъект, а другой — как

предикат.

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

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

Более того, в пику некоторым аспектам теории Лейбница следует сказать, что аналитический порядок предикатов — это порядок сосуществования и следования, в котором нет логической иерархии и который лишен характера всеобщности.

Члены предицирующей артикуляции, субъект — предикат, возникают внутри показывания.

Не вводится ли исподволь с материальной вещностью бытие — постоянное вещное наличие, — которое через последующее наделение сущего ценностными предикатами настолько не получает онтологического восполнения, что скорее эти ценностные черты сами оказываются лишь онтическими определенностями сущего, имеющего бытийный образ вещи?

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

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

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

Короче, метаморфоза — это освобождение несуществующей сущности в каждом положении вещей и освобождение инфинитива в каждом теле и качестве, каждом субъекте и предикате, каждом действии и страдании.

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

предикатов, характеризующих репрезентативную систему на непротиворечивость, и т.

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

Источник: библиотека Максима Мошкова

Факты и правила — Представление знаний

Логическое программирование — это направление современного про­грам­мирования, возникшее первоначально в рамках работ по ис­кусствен­ному интеллекту и получившее свое развитие во второй половине вось­мидесятых годов, благодаря японскому проекту ЭВМ пятого по­ко­ле­ния. Наиболее полное выражение идеи логического программирования наш­ли в языке Prolog (PROgramming in LOGic — программирование в терминах логики). Первоначальный вариант языка Prolog был разработан под руководством Алэна Кольмероэ (Alain Colmerauer) в Марсельском уни­верситете в 1972 году. В настоящее время существуют разнообразные версии для DOS (PDC Prolog, Arity Prolog и др.), Windows (Visual Prolog, Strawberry Prolog, Trinc Prolog и др.), Linux (Arity Prolog, Visual Prolog и др.).

Теоретической основой Prolog является раздел символьной логики, на­зы­ва­емый исчислением предикатов. Prolog присущ ряд свойств, ко­то­ры­ми не об­­ладают традиционные языки программирования, что делает его мощным сред­ством в области логического программирования. К та­ким свойствам от­но­сят­­ся механизм вывода с поиском и возвратом, встро­ен­ный ме­ханизм со­постав­ле­­ния с образцом и простая, но вы­ра­зи­тель­ная струк­тура данных с возможностью ее изменения. В Prolog отсут­ству­­ют ука­за­те­ли, операторы при­сва­ивания и GOTO. Естественным ме­то­дом про­грам­ми­ро­вания является ре­кур­сия.

Программа на Prolog есть совокупность утверждений. Утверж­де­ния состоят из целей. В конце утверждения ставится точка «.». Иногда ут­­вер­ж­дение называется предложением.

Основная операция Prolog — доказательство целей, входящих в ут­­верж­дение.

Существуют два типа утверждений:

  • факт — это одиночная цель, которая, безусловно, истинна;
  • правило состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.

Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.

Примеры фактов:

person (john).
мужчина (виктор).
нравиться (джон, мери).

Примеры правил:

человек (Х) :- мужчина(Х).
твистик(Кто_то) if человечек(Кто_то),
любит_танцевать(Кто_то, твист).

Выберем для реализации систему Visual Prolog (www.visual-prolog.com).

Решим задачу о родственных отношениях, так как Prolog хорошо приспособлен для обработки нечисловой информации.

Тот факт, что Том является родителем Боба, можно записать на Prolog так:

родитель(том, боб).

Здесь мы выбрали родитель в качестве имени отношения, том и боб — в качестве аргументов этого отношения. Записываем имена, как том, начиная со строчной буквы. Все дерево родственных отношений (семантическая сеть)

пам том

\ / \

боб лиз

/ \

энн пат

/

джим

описывается следующей программой на языке Visual Prolog:

domains
name=symbol
predicates
родитель(name,name)
clauses
родитель(pam,bob).
родитель(tom,bob).
родитель(tom,liz).
родитель(bob,ann).
родитель(bob,pat).
родитель(pam,jim).
goal родитель(bob,pat).

Для программирования необходимо

1. Запустить систему Visual Prolog.

Рис. 12.1. Окно Visual Prolog 5.0

2. Ввести программу File ® New.

3. Протестировать цель Project ® Test Goal.

На заданный вопрос: «Является Боб родителем Пат?» — система ответит yes (да), найдя такой факт в программе.

Другой вопрос: «Кто является родителем Лиз?»

goal родитель(X,liz).

Ответ системы

X=tom
1 Solution.

Вопрос «Кто дети Боба?» можно передать в такой форме:

goal родитель(bob, X).
Ответ
X=ann
X=pat
2 Solutions

Программе можно задавать и более общие вопросы: «Кто чей родитель?» Сформулируем его таким образом:

Найти X и Y такие, что X — родитель Y.

На Prolog это записывается так:

goal родитель(X,Y).

Система будет по очереди находить все пары вида «родитель-ребенок».

X=pam, Y=bob
X=tom, Y=bob
X=tom, Y=liz
X=bob, Y=ann
X=bob, Y=pat
X=pam, Y=jim
6 Solutions

Запрограммируем задачу.

Даны утверждения:

Зевс — отец Ареса. Гера — мать Ареса. Арес — отец Гармонии. 
Аф­ро­ди­та — мать Гармонии. Карид — отец Семелы.
Зевс — отец Диониса. Семела — мать Диониса. Божества — Зевс, Гера, Арес, Афродита. Гармония — царица.

Определить правила: женщина, мужчина, родитель, родители, дедушка, бабушка.

domains
name=string
predicates
отец(name, name) % отец (Кто, Чей)
мать(name, name) % мать (Кто, Чья)
божество(name) % божество(Имя)
царица (name) % царица (Имя)
clauses
отец("Зевс", "Арес").
отец("Арес", "Гармония").
отец("Карид", "Семела").
отец("Зевс", "Дионис").
мать( "Гера", "Арес").
мать("Афродита", "Гармония").
мать("Семела", "Дионис").
божество( "Зевс").
божество("Гера").
божество("Арес").
божество("Афродита").
царица ( "Гармония").

Определим правило женщина, исходя из только описываемого мира.

X является женщиной, если X — мать кого-либо Y или X — царица.
женщина (X) if мать (X,_).
женщина (X) if царица (X).

Аналогично правило мужчина.

X является мужчина, если X — отец кого-либо Y.
мужчина (X) if отец (X,_).

Правило родитель.

X родитель для Y, если X отец Y, либо X мать Y. 
родитель (X, Y) if отец (X, Y).
родитель (X, Y) if мать (X, Y).

Правило родители.

X и Y родители , если X родитель Z и Y родитель Z.
родители (X, Y) if родитель (X, Z),
родитель (Y, Z).

Цели можно поставить следующие.

goal женщина (Kto).% Кто является женщиной?
goal мужчина (Kto).% Кто является мужчиной?
goal родитель (X, "Дионис"). % Кто родители Диониса?

Решим задачу о родственных отношениях семьи Романовых, и найдем детей Алексея Михайловича.

domains
name=string
predicates
родитель(name, name) % родитель (Кто, Чей)
мужчина(name) % мужчина (Кто)
женщина(name) % женщина (Кто)
царь(name, integer, integer)
% царь(Имя, начало_правления, конец_правления)
goal родитель("Алексей Михайлович", X).
clauses
родитель("Михаил", "Алексей Михайлович").
родитель("Алексей Михайлович", "Федор").
родитель("Алексей Михайлович", "Иван").
родитель("Алексей Михайлович", "Софья").
родитель("Алексей Михайлович", "Петр I").
родитель("Петр I", "Алексей").
родитель("Екатерина II", "Павел I"). 
родитель("Петр III","Павел I").
мужчина("Михаил").
мужчина("Алексей Михайлович").
мужчина("Федор").
мужчина("Иван").
мужчина("Петр I").
мужчина("Алексей").
мужчина("Павел I").
мужчина("Петр III").
женщина("Софья").
женщина("Екатерина II").
царь("Михаил", 1613, 1645).
царь("Алексей Михайлович", 1645 ,1676).
царь("Федор",1676 ,1682).
царь("Иван",1682 ,1696).
царь("Софья",1682 ,1689).
царь("Петр I",1682 , 1725).
царь("Екатерина II", 1762, 1796).
царь("Петр III", 1761,1762 ).
царь("Павел I",1796 ,1801 ).
4 Solutions
 

Ответ системы:

 
X=Федор
X=Иван
X=Софья
X=Петр I
 

Найдем всех цариц с помощью составного вопроса.

goal царь(X,_,_),женщина(X).
X=Софья
X=Екатерина II
2 Solutions

Добавим несколько правил: брат (brother), сколько_правил (how_reign).

predicates
brother (name,name)
how_reign (name,integer)
clauses
brother(X, Y) if родитель(Z, X) and %(1)
родитель(Z, Y) and %(1)
мужчина(X) and %(2)
X<>Y. %(3)
how_reign(Name, H) :- царь(Name, h2, h3),
H=h3-h3. 

Правило определения брата можно прочитать так:

Для любых X и Y, X является братом Y, если

  • у X и Y есть общий родитель, и
  • X — мужчина, и
  • X сам себе не брат.

В процессе достижения цели Prolog осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Иногда требуется его ограничить или исключить вовсе.

Для этого в Prolog существует ограничивающая перебор цель «отсечение» (!), которая безусловна верна.

Найдем только одного сына Алексея Михайловича

goal родитель(“Алексей Михайлович”,Son),
мужчина(Son),!.
Son=Федор
1 solution

Опишем предикат, определяющий из двух целых чисел максимальное.

predicates
max(integer, integer, integer)
goal max(5,9, Max).
clauses
max(X,Y,Max) if X>=Y, Max=X.
max(X,Y,Max) if X<Y, Max=Y.

Эти правила являются взаимоисключающими. Если выполняется первое, второе обязательно потерпит неудачу. Можно видоизменить при помощи отсечения правила.

max(X,Y,X) if X>=Y, !.
max(X,Y,Y).

Prolog содержит стандартный предикат, выполнение которого закан­чивается всегда неудачей — fail. Предикат fail инициирует процесс бэктрекинга (backtracking), то есть поиска новых решений, или передоказательства целей. Покажем на примере.

domains
name=symbol
predicates
отец (name, name)
everybody
clauses
отец ("Leonard", "Katherine").
отец ("Carl", "Jason").
отец ("Carl", "Marilyn").
everybody if
отец (X, Y) and
write(X,"является для ",Y," отцом\n") and
fail.
goal everybody.

Ответ системы:

Leonard является для Katherine отцом
Carl является для Jason отцом
Carl является для Marilyn отцом
no
Цель everybody завершена неудачно.

Для реализации отрицания используется предикат not. Особенность его ис­пользования состоит в том, что все переданные пе­ре­менные должные быть свя­занными, то есть конкретизированными. Например, ответ на вопрос: «Леонард не отец Джейсону?» будет найден.

goal not(отец ("Leonard","Jason")). 
yes

Цель

goal not(отец (X,"Jason")).

не будет восприниматься системой. Можно переформулировать цель: «Кто из известных системе отцов не является отцом Джейсона?».

goal отец (X,_), not(отец (X,"Jason")).
X=Leonard
1 Solution

Таким образом, нельзя получить знание из незнания, и предикат not используется только для проверки целей.

В приведенных программах на Visual Prolog можно выделить и дополнить:

Секции:

Domains

% определение типов данных

Predicates

% определение предикатов (имен отношений)

Clauses

% определение фактов и правил

Goal

% целевое утверждение

Основная операция, выполняемая на Prolog, — это операция сопоставления (назы­ваемая также унификацией или согласованием). Операция со­по­став­ления может быть успешной или закончиться неудачей;

Переменные обозначаются последовательностью букв и цифр, на­чи­­нающейся с заглавной буквы. Особый вид переменной — анонимная переменная _, ис­поль­зуемая в ка­честве аргумента предиката, когда конкретное значение пе­ре­­менной несущественно. На переменные в правилах действуют кванторы общности. Переменные получают свои значения в результате сопоставления с константами в фактах или правилах. Переменные служат частью процесса со­поставления, а не «хранилищем» информации. Область действия пе­ре­мен­ной — ровно одно предложение;

Факты — это предикаты с аргументами-константами, обозначающие от­но­ше­ния между объектами или свойства объектов, именованными этими кон­стантами. Факты в программе считаются всегда безусловно истинными и служат основой доказательства, происходящего при выполнении программы;

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

<голова правила> :- <список подцелей>. 

или

<голова правила> if <список подцелей>.

ГЛАВА 6. ВСТРОЕННЫЕ ПРЕДИКАТЫ. «ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ» | Клоксин У

 

6.5. Создание структур и работа с компонентами структур

Обычно когда мы хотим задать в программе на Прологе операции со структурой определенного вида, то мы делаем это, «упоминая» некоторым образом подобную структуру. Это значит, что если предикат используется для обработки множества структур различного вида, передаваемых ему в качестве аргумента, то обычно мы обеспечиваем отдельное утверждение для каждого класса структур. Хорошим примером такого подхода является программа для символьного дифференцирования, которая будет рассмотрена в разд. 7.1. В этой программе используются отдельные утверждения для функторов +, -, * и так далее. Мы знаем заранее, какие структуры могут появиться, и обеспечиваем утверждения для каждой из них.

В некоторых программах мы не можем предвидеть заранее все возможные структуры. Это имеет место, например, при написании программы «красивой печати», которая могла бы печатать произвольные структуры языка Пролог, размещая их в нескольких строках и используя отступы. (См. разд. 5.1, где представлена такая программа для печати списков.) Так, например, возможно, мы захотели бы напечатать терм

книга(629,автор(бронте, эмили),вх)

следующим образом:

книга

 629

 автор

  бронте

  эмили

 вх

Важным моментом является то, что мы хотим, чтобы эта программа работала правильно, какую бы структуру мы ей ни задали. Понятно, что одна из возможностей сделать это – обеспечить отдельное утверждение для каждого функтора, какой только можно представить. Но это работа, которую мы никогда не завершим, потому что существует бесконечно много различных функторов! Написать подобную программу можно, используя встроенные предикаты для работы со структурами произвольного вида. Здесь мы опишем некоторые из них – это предикаты functor, arg и ‘=..’. Мы опишем также предикат name, выполняющий операции над атомами.

functor(T,F,N)

Предикат functor определен таким образом, что functor(T,F,N) означает, что Т – это структура с функтором F, имеющим N аргументов. Этот предикат можно использовать двумя основными способами, В первом случае аргумент Т уже имеет значение. Целевое утверждение считается несогласованным с базой данных, если Т не является ни атомом, ни структурой. Если Т – это атом или структура, то F сопоставляется с функтором этой структуры, а N присваивается значение, равное числу аргументов функтора. Заметим, что в данном контексте считается, что атом – это структура с числом аргументов 0. Ниже приведено несколько примеров целевых утверждений с предикатом functor:

?- functor(f(a,b,g(Z)),F,N).

Z = _23, F = f, N = 3

?- functor(a+b,F,N).

F = +, N = 2

?- functor([a,b,c],F,N).

F =., N = 2

?- functor(apple,F,N).

F = apple, N = 0

?- functor([a,b,c],’.’,3).

нет

?- functor([a,b,c],a,Z).

нет

Прежде чем перейти к обсуждению предиката arg, следует рассмотреть второй способ использования предиката functor. В этом случае первый аргумент целевого утверждения functor (Т, F, N) неконкретизирован. В этом случае два других аргумента должны быть конкретизированы, однозначно определяя функтор и число аргументов соответственно. Целевое утверждение такого вида всегда согласуется с базой данных, и в результате значением Т становится структура с указанными функтором и числом аргументов. Таким образом, это некоторый способ создания произвольных структур по заданным функтору структуры и числу ее аргументов. Аргументами такой структуры, созданной с помощью предиката functor, являются неконкретизированные переменные. Следовательно, эта структура будет сопоставима с любой другой структурой, имеющей тот же функтор и одинаковое число аргументов.

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

копирование(Старая, Новая):- functor(Cтapaя,F,N), functor(Hoвaя,F,N).

В этом определении подряд используются два целевых утверждения functor. Если целевое утверждение копирование имеет конкретизированный первый аргумент и неконкретизированный второй, то произойдет следующее. Первое целевое утверждение functor будет соответствовать первому способу использования этого предиката (так как первый аргумент этого предиката конкретизирован). Следовательно, F и N конкретизируются, получив в качестве значений функтор и число аргументов этой существующей структуры. Второе целевое утверждение functor соответствует второму способу использования этого предиката. На этот раз первый аргумент неконкретизирован, и информация, задаваемая F и N, используется для создания структуры Новая. Эта структура имеет те же функтор и число аргументов, что и Старая, но ее компонентами являются переменные. Таким образом, возможен следующий диалог:

?- копирование(sentence(np(n(john)), v(eats)),X).

X = sentence(_23,_24)

Мы используем подобную комбинацию целевых утверждений functor в определении предиката reconsult в разд. 7.13.

arg(N,T,A )

Предикат arg всегда должен использоваться с конкретизированными первым и вторым аргументами. Он применяется для доступа к конкретному аргументу структуры. Первый аргумент предиката arg определяет, какой аргумент структуры необходим. Второй аргумент определяет структуру, к аргументу которой необходим доступ. Пролог находит соответствующий аргумент и затем пытается сопоставить его с третьим аргументом предиката arg. Таким образом, цель arg(N,T,A) согласуется с базой данных, если N-й аргумент Т есть А. Давайте рассмотрим несколько целевых утверждений с arg.

?- аrg(2,отношение(джон,мать(джейн)),Х).

X = мать(джейн)

?- arg(1,a+(b+c),X).

X =а

?- arg(2,[a,b,c],X).

X = [b,c]

?-arg(l,a+(b+c),b).

нет

Иногда мы захотим использовать предикаты functor и arg в ситуации, когда возможные структуры уже известны. Это связано с тем, что структура может иметь так много аргументов, что просто неудобно каждый раз перечислять их все. Рассмотрим пример, в котором структуры используются для описания книг. Мы могли бы иметь отдельную компоненту для названия книги, ее автора, издательства, года издания и так далее. Будем считать, что результирующая структура имеет четырнадцать компонент. Мы могли бы написать следующие полезные определения:

является _ книгой(книга(_,_,_,_,_,_,_,_,_,_,_,_,_,_)).

название(книга(Т,_,_,_,_,_,_,_,_,_,_,_,_,_),Т).

автор(книга(_,А,_,_,_,_,_,_,_,_,_,_,_,_),А).

. . .

В действительности мы можем записать это значительно более компактно следующим образом:

является_книгой(Х):- functor(X, книга, 14).

название(Х,Т):- является_книгой(Х), arg(1,X,T).

автор(Х,А):- является_книгой(Х), arg(2,X,T).

. . .

X=..L

Предикаты functor и arg дают один из способов создания произвольных структур и доступа к их аргументам. Предикат «=..» предоставляет альтернативный способ, полезный в том случае, когда необходимо одновременно получить все аргументы структуры или создать структуру по заданному списку ее аргументов. Целевое утверждение X=..L означает, что L есть список, состоящий из функтора структуры X, за которым следуют аргументы X. Такое целевое утверждение может быть использовано двумя способами, так же как и целевое утверждение functor. Если X уже имеет значение, то Пролог создает соответствующий список и пытается сопоставить его с L. Напротив, если X неконкретизировано, то список будет использован для формирования соответствующей структуры, которая станет значением X. В этом случае голова списка должна быть атомом (этот атом станет функтором X). Ниже приведено несколько примеров целевых утверждений, содержащих =..:

?- имя(а,b,с) =.. X.

X = [имя,а,b,с]

?- присоединить([А|В],С, [A|D]) =..L.

A = _2, В = _3, С = _4, D = _5, L = [присоединить,[_2|_3],_4,[_2|_5]]

?- [a,b,c,d] =..L.

L = [‘.’,a,[b,c,d]].

?- (a+b) =.. L.

L = [+,a,b].

?- (a+b) =..

[+,A,B] A = а, В = b

?- [a,b,c,d] =..

[A|B] A = ‘.’, В = [a,[b,c,d]]

?- X =.. [a,b,c,d]

X = a(b,c,d).

?- X =.. [присоединить,[a,b,],[c],[a,b,c]].

X = присоединить([а,b],[с],[а,b,с])

Примеры использования предиката =.. приведены в разд. 7.12.

name(А,L)

В то время как предикаты functor, arg и =. . используются для формирования произвольных структур и доступа к их аргументам, предикат name используется для работы с произвольными атомами. Предикат name сопоставляет атому список литер (их ASCII кодов), из которых состоит этот атом. Данный предикат можно использовать как для определения литер, составляющих указанный атом, так и для определения атома, содержащего заданные литеры. Целевое утверждение name(A, L) означает, что литеры, образующие атом А, являются элементами списка L. Если аргументу А уже присвоено значение, то Пролог создает список литер и пытается сопоставить его с L. В противном случае Пролог использует список L для создания атома, который станет значением А. Приведем примеры использования предиката name:

?- name(apple,X).

X = [97,112,112,108,100]

?- name(X,[97,l12,112,108,100]).

X = apple

?- name(apple,»apple»).

да

?- name(apple,»pear»).

нет

В разд. 9.5 предикат name используется для доступа к внутренней структуре слов английского языка, представляемых атомами Пролога.

Введение в математическую логику

2.1Высказывания

2.1.1Примеры высказываний

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

Как бы определение 1. Высказывание — это утверждение с чётко определенным смыслом, которое может быть истинным или ложным.

Как обычно, проще привести несколько примеров.

Пример.
  • «2+2=5» — пример высказывания. Оно ложно.
  • «3>2» — ещё один пример высказывания. Оно истинно.
  • «5 — простое число» — ещё одно истинное высказывание.
  • «Множество простых чисел конечно» — это ложное высказывание.
  • «Если целое число простое и оно больше двух, оно нечётно» — истинное высказывание.
  • «Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел» — это высказывание, истинность которого в настоящий момент неизвестна (это так называемая бинарная проблема Гольдбаха).
  • «n — чётное число» — это не высказывание, потому что непонятно, чему равно n (здесь, конечно, под n подразумевается не собственно буква, а переменная, которая может принимать разные значения), и поэтому это утверждение не является ни ложным, ни истинным. С такого типа утверждениями (они называются предикатами) мы познакомимся чуть позже.

Вместо «истинно» или «ложно» используются и другие синонимичные выражения: верно (неверно), корректно (некорректно) и т. д.

2.1.2Операции с высказываниями

Из существующих высказываний можно делать новые высказывания с помощью логических операций (которые также называются операциями булевой алгебры). Пусть даны какие-то высказывания A и B.

Определение 1. Высказывание «верно по крайней мере одно из двух высказываний A или B (или оба)», называется дизъюнкцией высказываний A и B. Оно обозначается A∨B. Другой термин для дизъюнкции — логическое «ИЛИ».

Определение 2. Высказывание «верны оба высказывания A и B» называется конъюнкцией высказываний A и B. Оно обозначается A∧B. Другой термин для конъюнкции — логическое «И».

Определение 3. Высказывание «высказывание A неверно» называется отрицанием A. Обозначается ¬A. Другой термин — логическое «НЕ».

Если про каждое из высказываний A и B известно, является оно истинным или ложным, легко установить истинность их конъюнкции, дизъюнкции и отрицания. Например, если A истинно, то ¬A ложно. Если A и B оба истинны, то A∧B истинно, иначе оно ложно. И так далее. Эту информацию удобно записывать в виде табличек, которые называются таблицами истинности.

Таблица истинности для отрицания выглядит так:

A¬AИЛЛИ

Таблицы истинности для конъюнкции и дизъюнкции:

ABA∨BA∧BИИИИИЛИЛЛИИЛЛЛЛЛ

В дальнейшем нам понадобится ещё одна важная логическая операция, но пока остановимся на этих.

2.1.3Раскрытие скобок с отрицанием

Пусть A и B — какие-то высказывания. Рассмотрим высказывание ¬(A∨B). В каком случае оно истинно? Только в том случае, когда оба высказывания A и B ложны. Действительно, если хотя бы одно из них истинно, тогда их дизъюнкция (логическое ИЛИ) истинна и значит её отрицание ложно. Записывая это соображение в виде формулы, получаем такое равенство:

¬(A∨B)=(¬A)∧(¬B)

Аналогично можно рассмотреть высказывание ¬(A∧B). Чтобы оно стало истинным, достаточно, чтобы хотя бы одно из высказываний A или B было ложным: тогда их конъюнкция (логическое И) ложна и её отрицание истинно. Таким образом:

¬(A∧B)=(¬A)∨(¬B)

Можно сказать, что при раскрытии скобок, перед которыми стоит отрицание, знак ∨ меняется на ∧ и наоборот.

Эти правила преобразования формул в алгебре логики называются законами де Моргана.

2.1.4Логические операции в программировании

В распространённых языках программирования высказываниям соответствуют выражения, имеющие значения типа «булевская величина» (например, в Python это bool), то есть принимающие значения «истина» или «ложь» (True и False). Например, 2 + 3 == 4 имеет значение False, а 3 > 2True. К булевским значениям можно применять логические операторы and, or и not. Например, 2 * 0 == 1 or 3 > 2 имеет значение True.

2.2Предикаты и кванторы

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

Выше фигурировал пример утверждения «n — чётное число». Если задать вопрос, является оно истинным или ложным, вы скорее всего скажете, что вопрос не имеет смысла: как можно на него ответить, если не знаешь, чему равно n? Это пример утверждения, не являющегося высказыванием. Утверждения такого типа называются предикатами.

Как бы определение 2. Грубо говоря, предикат — это такое утверждение, которое зависит от одной или нескольких переменных, и становится высказыванием, если задать значения этих переменных.

Пример 1. Рассмотрим предикат «n — чётное число». Его можно обозначить какой-нибудь буквой, аналогично обозначению функций — например, E(n). При подстановке конкретного n предикат становится высказыванием, которое является истинным или ложным. Например, E(2) истинно, а E(17) — ложно. Подобно функциям, у предикатов есть «область определения» — множество значений, которые могут принимать переменные. Например, давайте считать, что областью определения для E(n) является множество натуральных чисел, n∈N (но можно было бы определить аналогичный предикат и для множества всех целых чисел).

Пример 2. Определим предикат D(k,n) — «n делится на k». Этот предикат зависит от двух переменных. Будем считать, что n∈N и k∈N. Например, D(2,3) — ложь, а D(2,4) — истина.

Пример 3. Ещё нам понадобится предикат S(x,y)=«x2=y», определенный для вещественных x и y. Он проверяет, что x2 равняется y.

Одни предикаты можно определять через другие. Например, если бы у нас был готовый предикат D, проверяющий делимость, и нам нужно было изготовить из него предикат E, проверяющий число на чётность, его легко можно было бы задать таким образом:

E(n)=D(2,n).

В следующем разделе мы познакомимся с ещё одним способом создания новых предикатов из существующих.

2.2.2Квантор всеобщности

Давайте рассмотрим предикат T(n)=D(1,n). Он проверяет, что натуральное число n делится на 1. Но все натуральные числа делятся на 1! Это можно сформулировать следующим образом: «для всех значений n предикат T(n) имеет значение „истина”». Есть специальный короткий способ записывать такого типа утверждения:

∀n:T(n).

Знак ∀ (перевёрнутая буква A, от all) называется квантором всеобщности. Он читается «для всякого». Часто после квантора пишут не просто переменную, но и её область определения:

∀n∈N:T(n).

Если область определения не указана, считается, что мы её указали при определении предиката или её можно понять из контекста. Вопрос 1. Рассмотрим утверждение ∀n∈N:E(n), где E(n) — предикат, проверяющий, что n чётное число. Что вы можете сказать про построенное таким образом утверждение?   Оно истинно.

Неверный ответ. Вы уверены? В этом утверждении сказано: «для любого натурального n верно, что n чётно». Иными словами, это утверждение можно переписать так: «все натуральные числа — чётны».

  Оно ложно.

Верный ответ. Да, потому что бывают нечётные числа. Например, E(3) — ложно.

  Невозможно определить его истинность, зависит от значения n.

Неверный ответ. Нет! В этом утверждении сказано: «для любого натурального n верно, что n чётно». Иными словами, это утверждение можно переписать так: «все натуральные числа — чётны». Это утверждение попросту неверно.

2.2.3Квантор существования

Совершенными числами называются натуральные числа, которые равны сумме всех своих положительных делителей, отличных от самого числа (так называемых «собственных делителей»).

Рассмотрим предикат R(n), проверяющий, является ли натуральное число n совершенным. (Иными словами, R(n) соответствует утверждению «n совершенное число».)

Если взять какое-то конкретное n, очень легко проверить, является ли оно совершенным. Например, число 10 имеет три собственных делителя, 5, 2 и 1, но 5+2+1=8≠10 — значит, оно не совершенное. Но существуют ли вообще совершенные числа? Иными словами, верно ли утверждение: «существует такое n, что R(n) имеет значение „истина”»?

Для формулирования таких утверждений также есть специальное короткое обозначение:

∃n:R(n)

или

∃n∈N:R(n).

Знак ∃ (перевернутая буква E, от exists) называется квантором существования. Читается просто «существует [такое]».

Аналогично квантору всеобщности (см. замечание 2), квантор существования «связывает» соответствующую переменную. Утверждение ∃n:R(n), хотя в нём фигурирует переменная n, не является предикатом, зависящим от n. Это просто высказывание, которое является истинным (если совершенные числа существуют), или ложным (если их нет).

Кстати, совершенные числа существуют. Например, число 6 совершенно. Это доказывает, что утверждение ∃n:R(n) является истинным.

2.2.4Кванторы и отрицание

Есть обобщение законов де Моргана на формулы с кванторами. Рассмотрим какой-нибудь предикат P(x). (Например, x принадлежит множеству всех крокодилов, а P(x) провряет, что крокодил x является красным.)

Рассмотрим высказывание ∀x:P(x) («все крокодилы красные»). Чтобы его опровергнуть (то есть доказать его отрицание), достаточно предъявить какого-нибудь крокодила, который бы не был красным. Иными словами, верно равенство:

¬(∀x:P(x))=(∃x:¬P(x))(2.1)

Аналогично, можно рассмотреть утверждение ∃x:P(x) («существует по крайней мере один красный крокодил»). Чтобы его опровергнуть, нужно перебрать всех крокодилов, и проверить, что каждый из них не является красным. Иными словами, верно такое равенство:

¬(∃x:P(x))=(∀x:¬P(x))(2.2)

Можно сказать, что при переносе знака отрицания через квантор он меняется на обратный: существование на всеобщность и наоборот.

2.3Кванторы и предикаты с несколькими переменными

2.3.1Связывание одной переменной

Рассмотрим предикат S(x,y)=«x2=y», определенный для вещественных x и y. Рассмотрим такое утверждение: ∃x:S(x,y). Что это за объект?

Если задать конкретное значение y, например, y=4, получается такая штука: ∃x:S(x,4) или попросту

∃x:x2=4

Иными словами, получается высказывание о том, что существует квадратный корень из числа 4. Это высказывание ни от чего не зависит и является верным (достаточно предъявить x=2).

Однако, можно выбрать другое значение y, например, положить y=−1. Тогда получается утверждение

∃x:x2=−1

Это утверждение неверно: мы знаем, что квадраты вещественных чисел неотрицательны, и значит не существует такого x, что его квадрат равен −1.

Вернёмся теперь к утверждению ∃x:S(x,y). Мы видим, что в в это утвреждение вместо y можно подставлять различные числа и получать разные высказывания — верные и неверные. Значит, перед нами предикат, зависящий от y. Обозначим его через Q(y). Можно записать:

Q(y):=(∃x:S(x,y))

Таким образом, из предиката с двумя переменными S мы получили предикат с одной переменной y, поскольку переменную x «связали» с помощью квантора. В высказывании ∃x:S(x,y) переменная y называется «свободной» (мы можем задавать её значения как хотим и получать разные высказывания), а переменная x — «связанной».

2.3.2Последовательное применение кванторов

Рассмотрим предикат G(n,m)=«n>m», определенный на множестве натуральных чисел. Введём новый предикат:

Z(m):=(∃n:G(n,m))=(∃n:n>m).

Теперь можно рассмотреть высказывание ∀m:Z(m). Его можно записать так:

∀m ∃n:n>m.(2.3)

Читается: «для всякого m существует такое n, что n>m».

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

Является ли оно истинным? Да, является. Действительно, возьмём любое m. Заметим, что для него предикат Z(m) верен, поскольку существует такое n (например, можно взять n=m+1), для которого n>m. (Действительно, m+1>m, каким бы ни было m.)

Словами это высказывание можно было бы записать так: «для всякого натурального числа найдётся большее его число». Эта формулировка с точки зрения привычного нам языка выглядит немножко неестественно и может возникнуть искушение сделать её более привычной, переформулировав таким образом: «найдется натуральное число, большее любого другого натурального числа». Однако, то, что в результате получилось — не переформулировка исходного утверждения, а совсем другое высказывание. Оно формально записывается так:

∃n ∀m:n>m(2.4)

Как видно, эта формулировка отличается от (2.3) только порядком следования кванторов. Однако, её смысл совсем иной. При доказательстве высказывания (2.3) мы для каждого конкретного n могли выбирать своё m, так, чтобы сделать предикат n>m справедливым. В высказывании (2.4) мы должны задать одно-единственное n, такое, что для него предикат n>m был бы верен для всех возможных m. Нетрудно видеть, что среди натуральных чисел такого n нет. Действительно, каким бы мы ни взяли n, можно положить m=n (или m=n+1, или m=n+2 и т.д.), и предикат n>m не будет верным. Видно, что порядок следования кванторов очень важен: он определяет порядок, в котором соответствующие переменные могут выбираться. В данном случае при изменении порядка кванторов получились разные результаты: утверждение с одним порядок истинное, а с другим ложное. Так бывает не всегда (придумайте пример, когда это не так), но важно понимать, что изменение порядка следования кванторов создаёт другое утверждение.

2.3.3Отрицание и серия кванторов

Мы уже опровергли утверждение (2.4), но давайте ещё раз более подробно поговорим, как мы это сделали. Чтобы опровергнуть утверждение с кванторами обычно проще всего записать к нему отрицание, а потом доказать это отрицание. Воспользуемся формулами из раздела 2. 2.4. Обозначим предикат ∀m:n>m через W(n). Утверждение (2.4) можно переписать в виде:

¬(∃n:W(n))

Применим к нему равенство (2.2):

¬(∃n:W(m))=∀n(¬W(m))=∀n(¬(∀m:n>m))=…(2.5)

¬(∃n:W(m))=∀n(¬W(m))==∀n(¬(∀m:n>m))=…(2.5)

Теперь можно к выражению ¬(∀m:m>m) применить формулу (2.1) и подставить результат в (2.5):

…=(∀n ∃m:¬(n>m))=(∀n ∃m:n⩽m).

Мы как бы последовательно перекинули знак отрицания сначала через первый квантор, а потом через второй. Каждый раз квантор менялся на противоположный. Наконец, отрицание оказалось записано перед предикатом n>m, но мы знаем, что отрицание к утверждение n>m — это утверждение, что n⩽m. Итак, отрицанием к высказыванию (2.4) является высказывание

∀n ∃m:n⩽m.

Докажем его. Для этого нужно научиться для всякого n предъявлять такое m, что n⩽m. Это просто: достаточно взять, например, m=n. С тем же успехом можно было бы взять m=n+1 или m=n+100.

2.4Импликация

Давайте рассмотрим такое утверждение: «если натуральное число делится на 4, то оно делится на 2» (обозначим его за A). Как мы знаем, это верное утверждение. Как его сформулировать на языке кванторов и предикатов? Давайте введём предикат Q(n), проверяющий, что n делится на 4. Раньше мы вводили предикат E(n), проверяющий чётность n. Поскольку речь про все натуральные числа, следует начать с квантора ∀n. Очевидно, дальше нужно написать какое-то утверждение с предикатами Q(n) и E(n), но какое?

Вероятно, здесь проще начать с отрицания. Что нам нужно было бы сделать, чтобы опровергнуть утверждение A? Нужно придумать такое n, чтобы оно делилось на 4, но при этом не делилось на 2. Именно такой контрпример, если бы он был построен, опроверг бы наше утверждение. Иными словами, нам нужно было бы предъявить такое n, что Q(n) выполняется, а E(n) нет, то есть верно утверждение Q(n)∧(¬E(n)). Итак, отрицание к A выглядит так:

¬A=(∃n:Q(n)∧(¬E(n)))

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

A=(∀n:(¬Q(n))∨E(n))(2.6)

Иными словами, мы утверждаем, что для всякого n выполняется следующее. Либо оно не делится на 4 (тогда ¬Q(n) является истинным: про числа, которые не делятся на 4, мы ничего не утверждаем, а если мы ничего не утверждаем, то нечему быть неверным), либо, если оно делится на 4 (¬Q(n) ложно), оно обязано делиться на 2 (чтобы вся дизъюнкция была истинной, если второй её аргумент ложный, то первый — в данном случае, E(n) — должен быть истинным).

Это ровно то, что мы хотим сказать.

Вопрос 2. Зачем городить такой огород? Почему нельзя было просто написать

∀n:P(n)∧Q(n)?(2.7)

  Можно было так и написать, формулы (2.7) и (2.6) эквивалентны.

Неверный ответ. А вот и нет. Например, утверждение A и формула (2.6) являются истинными, а утверждение в формуле (2.7) ложно. Действительно, возьмём, например, n=6. Оно не делится на 4, значит, Q(6) ложно, и значит для этого значения n конъюнкция ложна, а раз такое n нашлось, то и всё утверждение ложно. Проверьте, что этот пример не опровергает утверждение (2.6).

  Потому что это совсем другое утверждение, оно не эквивалентно A.

Верный ответ. Так и есть. Например, утверждение A и формула (2.6) являются истинными, а утверждение в формуле (2.7) ложно. Действительно, возьмём, например, n=6. Оно не делится на 4, значит, Q(6) ложно, и значит для этого значения n конъюнкция ложна, а раз такое n нашлось, то и всё утверждение ложно. Проверьте, что этот пример не опровергает утверждение (2.6).

В общем виде это формулируется так. Пусть есть два высказывания, A и B. Утверждения «из A следует B» или «A влечёт B» или «если A истинно, то B тоже истинно», формально записываются так: ¬A∨B. Иными словами, говоря «если A истинно, то B тоже истинно», мы говорим, что A может и не быть истинным, но нас этот случай, не интересует, мы про него никаких выводов не делаем (а значит, и ошибаться не можем), но если уж A истинно, то B обязано быть истинным.

Эта операция с высказываниями A и B настолько важна, что хотя она и выражается через конъюнкцию, дизъюнкцию и отрицание, у него есть специальное название — импликация (ср. с английским словом imply, влечёт), и специальное обозначение: A⇒B. Утверждение A называется посылкой, а утверждение B — заключением.

Давайте построим таблицу истинности для A⇒B (то есть ¬A∨B).

ABA⇒BИИИИЛЛЛИИЛЛИ

Эта таблица, и особенно её третья строчка, обычно ставит в тупик всех, кто её в первый раз видит. «Из лжи следует истина!» — как такое может быть? Дело в том, что если вы делаете утверждение A⇒B («Если A истинно, то B тоже истинно»), и A оказалось ложным, то это просто означает, что вы находитесь в ситуации, про которую вы ничего не утверждали. А раз ничего не утверждали, то не могли и ошибиться. И значит вы правы (ваше утверждение истинно), вне зависимости от того, является ли B истинным или ложным.

Возвращаясь к примеру, который мы разбирали раньше: «если число n делится на 4, то оно чётное». Рассмотрим число n=6. Для него посылка оказалась ложной (оно не делится на 4), и хотя заключение оказалось истинным (оно чётно), это никак не противоречит нашей импликации: она остаётся верна и в этом случае.

В дальнейшм мы будем постоянно пользоваться импликацией в доказательствах. Начнём прямо со следующей лекции.

2.5Заключение

Теперь у нас есть математический аппарат, своего рода язык, который позволяет аккуратно записывать и даже в какой-то мере автоматически анализировать довольно сложные утверждения. Мы рассматривали самые простые примеры, чтобы было понятно, как работает «механика» математической логики. Совсем скоро мы будем использовать её в условиях, максимально приближенных к боевым.
← Предыдущая глава Следующая глава →

Функция предиката, терминология и соглашение об именах

Автор Xah Lee. Дата: . Последнее обновление: .

Значение «предиката» в логике и информатике

в математике и программировании есть термин «предикат». В логике первого порядка «предикат» — это унарное отношение. Например, p (x) означает, что p (x) истинно. В псевдокоде вы утверждаете, что eval (f (x)) == True .

Но на языке программирования «предикат» означает просто функцию, возвращающую истину или ложь.

это важно и часто сбивает с толку. Вот конкретный пример. Предположим, вы хотите сказать, что 3 — целое число:

  • в логике предикатов, вы выражаете это как: isInteger (3)
  • в типичных языках программирования вы не можете сделать утверждение. Скорее, вы выражаете что-то вроде этого: if (isInteger (3) == True) {print ("good")} else {error ("что-то не так")}

В приведенном выше примере «isInteger» — это предикат, но их значение существенно отличается.

Соглашение об именах предикатов в компьютерных языках

Emacs Lisp и Common Lisp

в emacs lisp и Common Lisp, по соглашению, имена функций-предикатов заканчиваются на «p». Например, в emacs lisp у вас есть:

  • боб
  • болт
  • граница
  • буфер-live-p
  • модифицированный буфер-p
  • интерактивный вызов-p
  • заговор
  • eobp
  • eolp
  • fboundp
  • особенность
  • каталог-файлов-p
  • файл-существует-p
  • файл для чтения-p
  • функция p
  • целое число p
  • список
  • номер
  • набор-буфер-модифицированный-p
  • струна
  • символp
  • вектор,
  • зеро

в emacs lisp, не все функции, заканчивающиеся на p, являются предикатом. Например: {pop, defgroup, make-sparse-keymap, forward-sexp}

Схема Lisp и Clojure Lisp

в Scheme Lisp и Clojure Lisp принято называть предикат, оканчивающийся знаком вопроса «?».

это лучше. Потому что вопросительный знак более интуитивно понятен. Буква «р» непонятна, а термин «предикат» пришел из истории логики.

Язык Wolfram Language

в системе Mathematica они заканчиваются на «Q», что означает вопрос.

Идентификаторы Mathematica допускают использование только букв, а встроенные имена всегда начинаются с заглавной буквы.Итак, все встроенные имена имеют этот CamelCaseStyle.

Значит, они не могут использовать вопросительный знак ? . И поскольку p для предиката не интуитивно понятен, Q для вопроса.

примеров предиката Mathematica:

  • AlgebraicIntegerQ
  • Алгебраический блок Q
  • ArgumentCountQ
  • ArrayQ
  • AtomQ
  • Двоичное изображениеQ
  • CoprimeQ
  • DigitQ
  • Справочник
  • Q
  • DistributionDomainQ
  • Параметры распределения Q
  • EllipticNomeQ
  • EvenQ
  • ExactNumberQ
  • FileExistsQ
  • FreeQ
  • HermitianMatrixQ
  • Гипергеометрический PFQ
  • ImageQ
  • Неточный номер Q
  • Целое число Q
  • IntervalMemberQ
  • Обратный эллиптическийNomeQ
  • Неприводимый полином Q
  • LegendreQ
  • LetterQ
  • LinkConnectedQ
  • LinkReadyQ
  • ListQ
  • нижний корпус Q
  • Номер машины Q
  • MatchLocalNameQ
  • MatchQ
  • MatrixQ
  • MemberQ
  • ИмяQ
  • NumberQ
  • NumericQ
  • OddQ
  • OptionQ
  • заказаноQ
  • Перегородки Q
  • Полином Q
  • PositiveDefiniteMatrixQ
  • PossibleZeroQ
  • PrimePowerQ
  • PrimeQ
  • Q Гипергеометрический PFQ
  • Квадратичный Иррациональный
  • RootOfUnityQ
  • SameQ
  • УдовлетворительноQ
  • SquareFreeQ
  • StringFreeQ
  • StringMatchQ
  • StringQ
  • SymmetricMatrixQ
  • Синтаксис Q
  • ТавтологияQ
  • TensorQ
  • TrueQ
  • UnsameQ
  • Верхний корпус Q
  • ValueQ
  • VectorQ

[см. Mathematica vs Lisp Syntax]

Рубин

в Ruby, он взят из Scheme Lisp и заканчивается на «?».Например, вот методы предиката для целого числа:

  • ноль?
  • странно?
  • даже?
  • целое число?
  • экл?
  • реальный?
  • ненулевое?
  • между?
  • ноль?
  • испорченный?
  • ненадежный?
  • заморожено?
  • instance_variable_defined?
  • instance_of?
  • kind_of?
  • is_a?
  • response_to?
  • response_to_missing?
  • равно?

[см. Пример Ruby Tutorial]

Если у вас есть вопросы, положите 5 долларов на patreon и напишите мне.

Логика предикатов

Логика предикатов

Вычисления в логике предикатов

Пролог — это язык программирования, основанный на логике предикатов.

  • Программа Prolog пытается доказать цель, например, брат (Барни, x), из набора фактов и правил.
  • В процессе доказательства истинности цели, используя подстановку и другие правила вывода, Пролог заменяет значения переменных в цели, тем самым «вычисляя» ответ.

Как Prolog узнает, какие факты и какие правила использовать в доказательство?

  • Prolog использует унификацию для определения когда два предложения могут быть эквивалентны заменой переменных.
  • Используется процедура унификации для создания экземпляров переменных в целевом предложении на основании фактов и правил в базе данных.

Рупорные клаузулы

Чтобы упростить процесс разрешения в Prolog, заявления должны быть выражены в упрощенной форме, назвал статьи .

  • Отчеты составлены из терминов .
  • Каждое утверждение (предложение) имеет (максимум) один член слева сторона символа импликации (: -).
  • Каждый оператор содержит комбинацию из нуля или более терминов на Правая сторона.

В Прологе есть три типа операторов, соответствующие структуре используемой оговорки Хорна.

  • Факт — это предложение с пустой правой частью.
  • A вопрос (или цель ) — предложение с пустой левой частью.
  • A Правило — это пункт с условиями с обеих сторон.

Условия

В Prolog есть три вида терминов:

  • Константа — это атом или число. Атом — это строка символов в кавычках или строка букв, цифр, и подчеркивания, начинающиеся с строчной буквы. Число напоминает действительные или целые константы, используемые в большинстве языки программирования.
  • Переменная представляет собой строку букв, цифр и знаков подчеркивания. который начинается с заглавной буквы. Нет объявлений типов; типы обнаруживаются неявно переводчиком.
  • Структура представляет атомарное предложение предиката исчисление, и имеет вид «атом (список параметров)».

Факты и правила

Среда Prolog поддерживает набор из фактов и правил в своей базе данных.

  • Факты — аксиомы; отношения между терминами, которые предполагается будь настоящим.
  • Правила — это теоремы, позволяющие делать новые выводы.

Примеры фактов:

      мужчина (адам).
      женщина (анна).
      родитель (Адам, Барни).
   

Примеры правил:

      сын (X, Y): - родитель (Y, X), самец (X)
      дочь (X, Y): - родитель (Y, X), женщина (X)
   

Первое правило читается так: для всех X и Y X — сын Y. если существуют X и Y такие, что Y — родитель X, а X — мужской.

Второе правило читается так: для всех X и Y X — дочь Y. если существуют X и Y такие, что Y — родитель X, а X — женский.


Замечания о правилах Пролога

  • Подразумевается справа налево!
  • Область видимости переменной — это предложение, в котором она появляется.
  • Переменные, первое появление которых находится в левой части предложения имеют неявные универсальные кванторы.
  • Переменные, первое появление которых находится справа предложения имеют неявные кванторы существования.

Выполнение программы на прологе

Чтобы запустить программу на Прологе, пользователь должен задать вопрос (цель), сформулировав теорему (утверждая предикат), которая Интерпретатор Пролога пытается доказать.

Если предикат содержит переменные, интерпретатор печатает значения используемых переменных чтобы сделать предикат истинным.

Интерпретатор использует обратную цепочку для доказательства цели. Он начинается с того, что пытается доказать, и работает в обратном направлении, ища то, что будет подразумевать это, пока не дойдет до фактов.


Пример: наибольший общий делитель

Используя алгоритм Евклида, мы можем вычислить НОД двух натуральных чисел в Прологе следующим образом:

  / * Программа на прологе для вычисления НОД * /
  | gcd (A, 0, A). 
  | gcd (A, B, D): - (A> B), (B> 0), R - это A по модулю B, gcd (B, R, D).
  | gcd (A, B, D): - (A 
  
   

Первое правило - это базовый случай завершения рекурсивного определения.

Второе правило гарантирует, что первый аргумент является большим из двух, и это второй аргумент - положительное целое число, вычисляет остаток от A / B в R, и рекурсивно сопоставляет (находит) НОД меньшего аргумента и R.

Третье правило меняет порядок аргументов, так что аргумент большего размера становится первым.

Пролог пытается сопоставить правила по порядку, и предложения оцениваются слева направо. Если какое-либо предложение не выполняется (т. Е. Если A не больше B в правиле 2), тогда правило не работает.

Вот последовательность шагов системы доказательства Пролога пройдет, если A = 5 и B = 10:

      ? -gcd (5,10; D)
      (5> 10)
      gcd (10,5, D)
      (10> 5)
      (5> 0)
      R = 0
      gcd (5,0, D)
      D = 5
   

% PDF-1. 2 % 3056 0 объект > endobj xref 3056 79 0000000016 00000 н. 0000001935 00000 н. 0000002038 00000 н. 0000003071 00000 н. 0000003366 00000 н. 0000003490 00000 н. 0000003875 00000 н. 0000004154 00000 п. 0000005275 00000 н. 0000006389 00000 п. 0000006682 00000 н. 0000006811 00000 н. 0000006935 00000 п. 0000007051 00000 н. 0000007075 00000 н. 0000008344 00000 п. 0000008470 00000 н. 0000008494 00000 п. 0000009653 00000 п. 0000009677 00000 н. 0000010785 00000 п. 0000010809 00000 п. 0000011928 00000 п. 0000011952 00000 п. 0000013071 00000 п. 0000013372 00000 п. 0000014497 00000 п. 0000014521 00000 п. 0000015707 00000 п. 0000015731 00000 п. 0000016870 00000 п. 0000017142 00000 п. 0000017435 00000 п. 0000017459 00000 п. 0000018660 00000 п. 0000018682 00000 п. 0000018704 00000 п. 0000018727 00000 п. 0000019915 00000 п. 0000019938 00000 п. 0000020937 00000 п. 0000020961 00000 п. 0000023343 00000 п. 0000023365 00000 п. 0000023663 00000 п. 0000023685 00000 п. 0000023988 00000 п. 0000024011 00000 п. 0000025005 00000 п. 0000025029 00000 п. 0000026527 00000 п. 0000026551 00000 п. 0000029980 00000 н. 0000030004 00000 п. 0000034411 00000 п. 0000034435 00000 п. 0000038876 00000 п. 0000038900 00000 п. 0000042966 00000 п. 0000042990 00000 п. 0000047049 00000 п. 0000047073 00000 п. 0000050429 00000 п. 0000050452 00000 п. 0000050999 00000 н. 0000051023 00000 п. 0000054645 00000 п. 0000054669 00000 п. 0000056555 00000 п. 0000056579 00000 п. 0000060909 00000 п. 0000060933 00000 п. 0000065302 00000 п. 0000065326 00000 п. 0000068704 00000 п. 0000068728 00000 п. 0000070976 00000 п. 0000002104 00000 п. 0000003048 00000 н. трейлер ] >> startxref 0 %% EOF 3057 0 объект > endobj 3058 0 объект > endobj 3133 0 объект > ручей HS] hSI> & wFG {d7mSlm} hq ׶ IM $ Tjuh | YVIDDAQXA}.$. xg osΜ | 9wN

Реактивное программирование - Операторы и функции (Часть 1)

Реактивное программирование - Операторы и функции (Часть 1)

Операторы и функции - Часть 1

В реактивном программировании операторы берут один или несколько входных потоков и возвращают новый поток. Некоторые операторы могут принимать дополнительные аргументы, например функции , :

.
  • функция проекта ,
  • функция предиката ,
  • аккумуляторная функция и др.

Эти функции не должны работать с потоком ввода или вывода: они обычно просто преобразуют, сравнивают или комбинируют значения. Операторы работают с потоками вместе с этими функциями.

Проект и предикат

Как вы маркируете функцию (например,Функция «проект» или «предикат») зависит от того, как вы ее используете.

Функция, которая:

  • принимает несколько значений
  • и возвращает одно новое значение любого типа

может использоваться как функция проекта на , объединяющая операторов (например, combLatest или zip).

Функция, которая:

  • принимает одно значение
  • и возвращает одно новое значение любого типа

может использоваться как функция проекта с картой .

Функция, которая:

  • принимает одно значение
  • и возвращает одно новое значение типа boolean ( ✔ истина или ✘ ложь )

может использоваться как функция предиката для фильтрующих операторов (например, filter, takeWhile или skipWhile)

Как вы могли заметить, функция, используемая как предикат , также может использоваться как функция проекта в операторе карты:

В этом примере функция n n == 1 , которая возвращает ✔ истина или ✘ ложь , используется как аргумент для карты как проекта и для фильтра как предикат.В итоге:

  • map возвращает новый поток логических значений в соответствии с результатом этой функции проекта
  • фильтр возвращает новый поток отфильтрованных значений, где значения могут пройти, только если этот предикат возвращает ✔ истина

Сводка

  • Некоторые операторы могут принимать функции в качестве аргументов. Эти функции не должны работать с потоком ввода или вывода. Операторы делают.
  • Как вы маркируете функцию (например, «проектная» или «предикатная» функция), зависит от того, как вы ее используете. Функция сама по себе не является функцией проекта или предикатом .

См. Также


карта и фильтр


аккумулятор

Адвокат-фрилансер.Анимированная графика с кодом. JavaScript и Elm. cedricsoulas.com

Подпишитесь на рассылку новостей

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

книга программирования

Дополнительные уроки

Слон в Нанте (Les Machines de l'île)

Сделано во Франции, Нант

Присоединяйтесь к списку рассылки | Смотрите на Github

@CedricSoulas | Седрик. [email protected]

Седрик Сулас © 2017-2020 | Упоминает légales

условных выражений и предикатов

условных выражений и предикатов
Далее: Пример: квадратные корни по Up: Элементы программирования Предыдущая: Модель замещения для


Условные выражения и предикаты

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

Эта конструкция называется анализ случая , и в Лиспе есть специальная форма для обозначения таких случаев анализ. Это называется cond (что означает `` условный ''), и он используется следующим образом:

(определить (абс x)
  (усл ((> x 0) x)
        ((= х 0) 0)
        ((<х 0) (- х))))
 
Общая форма условного выражения:
(конд (p  1  e  1 )
      (п.   2  e  2 )
      
      (п   n   e   n  ))
 
состоящий из символа cond, за которым следует пары выражений в скобках (p e) называется статьи .Первое выражение в каждой паре - это предикат - то есть выражение, значение которого интерпретируется как либо правда, либо ложь.

Условные выражения оцениваются следующим образом. Предикат p 1 оценивается первым. Если его значение ложно, то p 2 . Если значение p 2 также ложно, то p 3 оценивается. Этот процесс продолжается до тех пор, пока предикат не будет найдено, значение которого истинно, и в этом случае интерпретатор возвращает значение соответствующего последовательное выражение e предложение как значение условного выражения.Если ни один из p оказывается истинным, значение cond равно неопределенный.

Слово предикат используется для процедур, возвращающих истину. или false, а также для выражений, которые оцениваются как истинные или ложные. Процедура абсолютного значения abs использует примитивный предикаты>, <и =. Это два числа в качестве аргументов и проверьте, является ли первое число, соответственно, больше, меньше или равно второму числу, возвращает истину или ложь соответственно.

Другой способ написать процедуру абсолютного значения:

(определить (абс x)
  (усл ((
что может быть выражено на английском языке как `` Если  x  меньше нуля
отдача -  х ; в противном случае верните  x . ''
Остальное - особый символ
который можно использовать вместо p в последнем предложении
конд. Это приводит к тому, что cond возвращает в качестве своего значения значение
соответствующий e всякий раз, когда все предыдущие предложения были
обошел.Фактически, любое выражение, которое всегда дает истинное значение
значение можно использовать как p здесь.

 

Вот еще один способ написать процедуру абсолютного значения:

(определить (абс x)
  (если (
Здесь используется специальная форма if, ограниченный тип условного
который можно использовать, когда есть точно
два случая по делу
анализ.  Общая форма выражения if:

 
(если предикат последовательная альтернатива)
 
Чтобы оценить выражение if, интерпретатор начинает с вычисления то предикатная часть выражения.Если предикат оценивается как истинное значение, интерпретатор затем оценивает то консеквент и возвращает его значение. В противном случае он оценивает то альтернатива и возвращает его значение.

Помимо примитивных предикаты, такие как <, = и>, есть логические операции композиции, которые позволяют нам построить составные предикаты. Три наиболее часто используемых:

    (и e 1 ... e n )

    Переводчик оценивает выражения e по одному, в порядке слева направо.Если любой e оценивается как ложь, значение и выражение ложно, а остальные е не оцениваются. Если все e имеют истинные значения, значение и выражение - это значение последнего.

    (или e 1 ... e n )

    Переводчик оценивает выражения e по одному, в порядке слева направо. Если любой e дает истинное значение, это значение возвращается как значение выражения или, а остальные е не оцениваются.Если все e имеют значение false, значение выражения или ложно.

    (Примечание)

    Значение выражения not истинно когда выражение e принимает значение false, иначе - false.

Обратите внимание, что and и or являются специальными формами, а не процедурами, потому что не обязательно все подвыражения оцениваются. Не обычная процедура.

В качестве примера того, как они используются, условие, что число x быть в диапазоне 5 < x <10 может быть выражено как

(и (> x 5) (
В качестве другого примера мы можем определить предикат для проверки того,
число больше или равно другому как

 
(определить (> = x y)
  (или (> x y) (= x y)))
 
или, альтернативно, как
(определить (> = x y)
  (не (

 

Упражнение. Ниже представлена ​​последовательность выражений. Какой результат выводит интерпретатор в ответ на каждый выражение? Предположим, что последовательность должна быть оценена в порядке в котором он представлен.

10

(+ 5 3 4)

(- 9 1)

(/ 6 2)

(+ (* 2 4) (- 4 6))

(определите 3)

(определите b (+ a 1))

(+ а б (* а б))

(= а б)

(если (и (> b a) ( b a) b a))

(* (cond ((> a b) a)
         ((<а б) б)
         (иначе -1))
   (+ 1))
 

Упражнение. Переведите следующее выражение в префиксную форму

Упражнение. Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумма квадратов двух больших чисел.

Упражнение. Обратите внимание, что наша модель оценки допускает комбинации, операторы являются составными выражениями. Используйте это наблюдение, чтобы опишите поведение следующей процедуры:

(определить (a-plus-abs-b a b)
  ((если (> b 0) + -) a b))
 

Упражнение. Бен Битдиддл изобрел тест, чтобы определить, подходит ли переводчик он сталкивается с использованием оценки аппликативного порядка или нормального порядка оценка. Он определяет следующие две процедуры:

(определить (p) (p))

 

(определить (тест x y) (если (= x 0) 0 у))

Затем он оценивает выражение
(тест 0 (p))
 
Какое поведение Бен будет наблюдать с переводчиком, использующим аппликативный порядок оценки? Какое поведение он будет наблюдать с интерпретатор, использующий оценку нормального порядка? Поясните свой ответ.(Предположим, что правило оценки для специальной формы if является то же самое, использует ли переводчик нормальный или аппликативный порядок: Сначала вычисляется выражение предиката, а результат определяет, стоит ли оценивать консеквент или альтернативное выражение.)

Далее: Пример: квадратные корни по Up: Элементы программирования Предыдущая: Модель замещения для
Райан Бендер
2000-04-17

CSCI 305: Языки программирования | CSCI305.github.io

Пролог, часть 1

Чтение: Webster Ch. 19

Инструкции

  1. Установите Prolog в вашу систему
  2. Посмотреть это видео - (19:04)
  3. Посмотреть это видео - (16:09)
  4. Посмотреть это видео - (19:57)
  5. Посмотреть это видео - (15:37)
  6. Просмотр слайдов лекций
  7. Просмотрите пример кода
  8. Посещайте занятия и выполните упражнения в классе
  9. Проверьте свои знания

В классе упражнения

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

Упражнение 1

Определите предикат isMember так, чтобы isMember (X, Y) сообщал, что элемент X является членом набора Y . Не используйте предикаты предопределенного списка.

Проверьте свои знания:
Решение:
  isMember (X, [X | _]).
    isMember (X, [_ | Хвост]): - isMember (X, Tail). 
Упражнение 2

Определите предикат isUnion так, чтобы isUnion (X, Y, Z) сообщал, что объединение X и Y равно Z . Не используйте предикаты предопределенного списка. Ваш предикат может выбрать фиксированный порядок для Z . Если вы запросите isUnion ([1,2], [3], Z) , он должен найти привязку для Z , но это не обязательно будет успешным на обоих isUnion ([1], [2], [1, 2]) и isUnion ([1], [2], [2, 1]) .Ваш предикат может не работать, если X или Y являются несвязанными переменными.

Проверьте свои знания:
Решение:
  isUnion ([Head | Tail], Y, Z): - isMember (Голова, Y), isUnion (Tail, Y, Z). 
    isUnion ([Head | Tail], Y, [X | Z]): - not (isMember (Head, Y)), isUnion (Tail, Y, Z).
    isUnion ([], Y, Y).
  
Упражнение 3

Определите предикат isIntersection , чтобы isIntersection (X, Y, Z) указывал, что пересечение X и Y равно Z .Не используйте предикаты предопределенного списка. Ваш предикат может выбрать фиксированный порядок для Z . Ваш предикат может не работать, когда X или Z являются несвязанными переменными.

Проверьте свои знания:
Решение:
  isIntersection ([Head | Tail], Y, [Head | Z]): - isMember (Head, Y), isIntersection (Tail, Y, Z).
    isIntersection ([Head | Tail], Y, Z): - not (isMember (Head, Y)), isIntersection (Tail, Y, Z).
    isIntersection ([], _, []).
  

CSCI 3675 практических вопросов для викторины 5

  • Что является одним из важных мотивов для включения исключения обработка на языке программирования?

    Ответ

  • Как реализована обработка исключений на типичном языке, например ява?

    Ответ

  • Отслеживание с возвратом и обработка исключений - одно и то же? Например, можете ли вы использовать механизм обработки исключений Java делать возврат?

    Ответ

  • Используя поиск с возвратом, напишите фрагмент программы Cinnameg, который будет распечатать все решения ( x , y ) уравнения x y - 2 x 2 + y = 10, где x и y являются целыми числами в диапазоне 0 ,. .., 100. Не используйте петлю или рекурсия. Когда это будет сделано, фрагмент вашей программы может выйти из строя.

    Ответ

  • Унификация - это форма сопоставления с образцом. Какой из следующее не характеристика унификации?

    1. Объединение никогда не изменяет привязку связанной переменной.
    2. Объединение симметричное; объединение A с B имеет точно такой же эффект, как и объединение B с A.
    3. Unification выполняется очень медленно и редко используется во время вычисления логических программ.
    4. Unification может связывать несвязанные переменные.

    Ответ

  • Верно или неверно.

    1. Когда переменная встречается в цели логического программирования, переводчика спрашивают, справедлива ли эта цель для всех значения переменной.

      Ответ

    2. Когда переменная встречается в логическом программировании аксиома , интерпретатору говорят, что аксиома верна для всех значения переменной.

      Ответ

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

      Ответ

  • Объясните отрицание как отказ. Какова его цель и как это работает?

    Ответ

  • Всегда ли отрицание как неудача правильно логическое отрицание?

    Ответ

  • Показать дерево поиска логического программирования для цели (член (X, [3,4,5]), член (X, [4])) до точки, где успех найден.Определение предиката-члена следующее: написано в синтаксисе Пролога.

          член (M, [M | X]).
          член (M, [X | T]): - член (M, T).
     

    Ответ

  • В стиле логического программирования напишите аксиомы для вычислений. префикс предиката (X, Y), который верен только тогда, когда список X является префиксом списка Y. Например, префикс ([2,4,6], [2,4,6,8,10]) истинен. Каждый список является префиксом самого себя.

    Ответ

  • В стиле логического программирования напишите аксиомы для вычислений. предикат allsame (X), который истинен только тогда, когда все члены списка X такие же.Например, allsame ([5,5,5]) верно, как и все то же самое ([a, a]), но все равно ([2,4,4]) ложно. Обратите внимание, что allsame ([]) истинно, и allsame ([b]) истинно.

    Ответ

  • В стиле логического программирования напишите аксиомы для вычислений. предикат samelength (X, Y), что верно только тогда, когда X и Y являются списками одинаковой длины.

    Ответ

  • Два человека являются двоюродными братьями, если у них есть общие бабушка и дедушка, но они не одно и то же, и не братья и сестры.Использование предиката прародителя ( X , Y ), что означает, что X прародитель Y и предикатный родной брат ( X , Y ) Это означает, что X и Y являются братьями и сестрами, напишите определение двоюродного брата ( X , Y ), используя нотацию Пролог, Это означает, что X и Y являются двоюродными братьями.

    Ответ

  • Предикат добавления определяется в Прологе следующим образом.

      добавить ([], Y, Y).
      append ([A | X], Y, [A | Z]): - добавляем (X, Y, Z).
     
    Вы хотели бы определить предикат double (X), что верно, если list X имеет вид Y ++ Y для некоторого Y. Например, double ([a, b, c, a, b, c]) истинно, но double ([a, b, c, a]) ложно.

    Что из перечисленного является правильным определением слова double в Прологе?

    1. двойной (X): - добавить (X, X, Y).
    2. двойной (X): - добавить (Y, Y, X).
    3. двойной (X): - добавить (X, Y, X).
    4. двойной (X): - добавить (Y, X, X).

    Ответ

  • Используя правильное определение предиката double из предыдущего упражнения, может ли интерпретатор Пролога обрабатывать целевой дубль (Z), где Z - несвязанная переменная? Если да, то что он будет делать? Если нет, то почему?

    Ответ

  • Вы хотите написать определение предикатного члена, где member (X, L) истинно, если X является членом списка L.