Что такое предикат в логике
Предикаты и кванторы
Вы будете перенаправлены на Автор24
Понятие предиката
Предикатом в программировании является функция, которая принимает один или более аргументов и возвращает значения булева типа.
Предикат называется тождественно-истинным, если на любом наборе аргументов он принимает истинное значение:
Предикат называется тождественно-ложным, если на любом наборе аргументов он принимает ложное значение:
Предикат называется выполнимым, если хотя бы на одном наборе аргументов он принимает истинное значение.
Примеры предикатов
Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.
Готовые работы на аналогичную тему
Операции над предикатами
Рассмотрим применение операций алгебры логики к предикатам.
Логические операции:
Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.
Кванторы
Чаще всего используют кванторы:
В математической логике существует понятие связывание или квантификация, которые обозначают приписывание квантора к формуле.
Примеры применения кванторов
С помощью квантора всеобщности можно записать следующие ложные высказывания:
который будет иметь вид:
Для записи истинных высказываний используем квантор существования:
Запись будет иметь вид:
Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.
Операции над кванторами
Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов:
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них:
Получи деньги за свои студенческие работы
Курсовые, рефераты или другие работы
Автор этой статьи Дата написания статьи: 07 04 2016
Логика: предикатная, формальная и сентенциальная. Кванторы и возникновение информатики
1 | Введение
Логика, как эпистемологический инструмент, — исследующий знание как таковое, — изобретена независимо в трёх отдельных государствах: Греции (Аристотелем), Китае (до правления Цинь Шихуанди) и Индии. В последних двух государствах логика не распространилась настолько, чтобы получить полноценное развитие. В античной же Греции логика сформировалась в своих основах столь определённо, что дополнилась только через 2 тысячелетия.
Значительные изменения в греческую логику, помимо Буля, Моргана и Рассела, внёс Фреге — самая важная фигура основателей формальной семантики. Он разработал логику предикатов и 2 вида кванторов, попытавшись создать «логически совершенный язык» о котором мечтал Лейбниц. Значимой личностью является также Гёдель, который открыл знаменитые две теоремы о неполноте, описывающие невозможность объединения множества доказуемых утверждений со множеством истинных. Он утверждал, что доказательства математики зависят от начальных предположений, а не фундаментальной истины, из которой происходят ответы. Одна из главных идей его работ состоит в том, что ни один набор аксиом, — в том числе математических, — не способен доказать свою непротиворечивость.
На этом этапе некоторые заметят влияние платонизма на австрийского логика. Совершенно верно, ведь Гёдель не раз заявлял о влиянии метафизики Платона на собственную деятельность. Но сам Платон развитию формальной логики способствовал лишь косвенно: в истории он вносит вклад в развитие другого направления — философской логики. Платоном созданы вопросы, на которых основывается вся западная академическая философия вплоть до наших дней. Философия, в том виде, котором она известна, возникла только благодаря учителю Аристотеля.
Платон — учитель Аристотеля
В другие периоды в логику также вносили дополнения:
античной школой стоицизма введены термины «модальности», «материальной импликации», «оценки смысла и истины», которые являются задатками логики высказываний;
также средневековыми схоластами введены несколько понятий;
Но главное, что сами логические операции не изменились. «Органон» Аристотеля, как сборник из 6 книг — первоисточник, где подробно описаны главные логические законы. «Органон» (с древнегреческого ὄργανον), означает — инструмент. Аристотель считал, что логика является инструментом к познанию. Он объединяет методом получения информации такие науки:
Физика — наука о природе;
Метафизика — наука о природе природы;
Биология — раздел физики, наука о жизни;
Психология — раздел физики, наука о душе;
Кинематика — раздел физики, наука о движении;
2 | Терминология
У каждой из наук должен быть идентичный фундамент в способе получения гнозисов (знаний), который позволит упорядочить информацию и вывести новые силлогизмы (умозаключения). Только таким образом получится прогресс в познании истины. Без логики наука была бы похожа на коллекционирование фактов, ибо информация бы не поддавалась анализу.
Сам Аристотель находит логике как средству убеждения иное применение: в риторике, спорах, дебатах, выступлениях и т.д., описывая это в труде «Риторика». В западной философии принято давать чёткие определения перед рассуждениями, поэтому определимся с терминами. Логика — наука о правильном мышлении.
В языковой зависимости возникают трудности трактовки термина «наука», но даже в оригинальном названии труда Фридриха Гегеля «Наука логики» — «Wissenschaft der Logik», употребляется слово «наука» (Wissenschaft). Поэтому придём к консенсусу и будем считать, что научной можно назвать ту дисциплину, в которой возможны открытия, исследование и анализ. Логика в таком случае — наука, ибо внутри неё возможно совершать открытия. Яркий пример — комбинаторика Лейбница.
Слово «правильный» веет нормативными коннотациями: правильное поведение, правильное выражение лица, и т.д. Перечисленное соответствует некоторым критериям и логика выставляет их (критерии) для правильного мышления.
Слово «мышление» понимается на интуитивном уровне, но чёткое объяснение затруднительно, обширно и иногда не объективно.
Бюст Аристотеля
3 | Формальная и неформальная логика
Первоначально, деление логики происходит на формальную и неформальную. Формальная логика отличается тем, что, в отличие от неформальной, записывается уравнениями. Неформальная же логика пишется выражениями в форме языка, поэтому она подходит для риторики, а формальная логика для абстрактных наук.
Формальная логика равным образом делится на дедуктивную и индуктивную. Они различаются тем, что в дедуктивном аргументе истинность условий гарантирует истинность умозаключения или вывода. В индукции же, при истинности условий одинаково возможен ложный и истинный вывод.
Законы формальной логики:
1. Закон тождества (А = А): эквивокация или двусмысленность недопустимы. Нельзя подменять одно понятие, другим.
2. Закон непротиворечия (А ∧ ¬А = 0): одно и то же утверждение не может быть истинным и ложным одновременно.
3. Закон исключения третьего или бивалентности (А ∨ ¬А = 1): утверждение может быть либо истинным, либо ложным — третьего не дано.
Принципы формальной логики:
1. Принцип достаточного обоснования: достаточными являются такие фактические и теоретические обоснования, из которых данное суждение следует с логической необходимостью.
4 | Сентенциальная логика (алгебра высказываний)
Базовые операции сентенциальной логики — логики высказываний, где заглавная буква означает предложение:
Отрицание (Утверждение ¬A истинно тогда и только тогда, когда A ложно): если имеем утверждение «А» и имеем утверждение «не А», то, когда утверждение «А» будет истинным — утверждение «не А» будет ложным. Также и когда утверждение «А» будет ложным — утверждение «не А» будет истинным.
Конъюнкция (Утверждение A ∧ B истинно, если и A, и B — истинны. Ложно в противном случае): в английском языке — союз «and/&»; в русском — «и». В утверждении «А и В», между «А» с «В» стоит знак конъюнкции — «∧». Утверждение «А и В» является истинным, если «А» с «В» являются истинными одновременно. Если хоть один элемент ложен, то всё утверждение ложно. «А и В» подразумевает, во-первых: истинность «А», во-вторых: истинность «В».
Дизъюнкция (Утверждение A ∨ B верно, если A или B (или оба) верны. Если оба не верны — утверждение ложно): в английском языке — союз «or»; в русском — «или». Существует два типа дизъюнкции — включающая и исключающая (в логике используется включающее «или»). Условия таковы, что утверждение «А или В» будет истинным, когда один или оба элемента истинны, но никогда — когда оба элемента ложны. Это противоречит нашему обыденному мышлению, т.к. когда спрашивают: «Чай или кофе?» мы выбираем один элемент, но в логике подразумевается выбор не только одного, а нескольких возможных.
Импликация (Утверждение A ⇒ B ложно, только когда A истинно, а B ложно): в английском языке — «therefore»; в русском языке — «следовательно». Подразумевает истинность одного элемента при истинности другого. Потому что условия истинности соблюдаются всегда, кроме случая, когда «А» истинно, а «B» ложно. Поэтому утверждение: «А» ложно, следовательно «B» ложно — истинно. Покажется, что когда «А» ложно, а «В» истинно — не соблюдаются условия, но это не так. Если вы скажете, что после дождя промокните — это утверждение будет истинным вне зависимости от того, пошёл дождь или нет.
Эквивалентность (Утверждение A ⇔ B истинно, только если оба значения A и B ложны, либо оба истинны): если истинно утверждение «А, следовательно В» и истинно утверждение «В, следовательно А», то истинными являются выражения «А эквивалентно В» и соответственно «В эквивалентно А». Условия истинности соблюдаются в случаях, когда оба элемента истинны или оба ложны.
Значение переменных
5 | Предикатная логика первого порядка
В XX веке, после добавлений в область логики работ Лейбница и Фреге, на основе этой дисциплины создаётся новая — информатика. Программирование сохраняет преемственность с видоизменённой логикой Аристотеля — предикатной логикой, описательная способность которой выше, чем у логики высказываний (сентенциальной).
Прежде чем разобрать этот новый тип логики, поговорим об её отличии от сентенциальной. Главная особенность предикатной логики, что заглавными буквами обозначаются предикаты, а не целые высказывания. Можно сказать, что предикат — это математическая функция, которая «накладывает» множество субъектов на множество утверждений.
Высказывание «Я пошёл в зоопарк» — состоит из субъекта и предиката. В нём субъект — «Я», а предикат — то, что остаётся кроме субъекта («пошёл в зоопарк»). Субъект — тот, кто совершает действие в предложении или имеет выраженное свойство; предикат — всё оставшееся. Таким образом, если в сентенциальной логике высказывание «Я пошёл в зоопарк» выражалось бы одной заглавной буквой, то в логике предикатов использовались бы две буквы (заглавная и подстрочная): «P» — для предиката; «x» — для субъекта. Субъекты обозначаются переменной («x»), потому что в предикатной логике появляются две относительно новые операции: универсальный и экзистенциальный кванторы. Особенность кванторов заключается в том, что ими возможно записать выражение истинное при всех возможных переменных «х» или хотя бы при одном.
Универсальный квантор (квантор всеобщности) обозначается символом — «∀», с указанием переменной под ним. Возьмём утверждение «Все пингвины чёрно-белые». В логике высказываний оно бы выражалось как «X ⇒ P», где «X» — нечто являющееся пингвином, а «P» — нечто являющееся чёрно-белым. В предикатной логике же используются субъекты и предикаты, поэтому нечто являющееся пингвином (субъект), обозначалось бы переменной «х» снизу под предикатом. «»х» — является пингвином, следовательно, является чёрно-белым». Записывается так: P(х) ⇒ B(х), где P(х): х — пингвин; B(х): x — чёрно-белый.
Однако этого недостаточно, ведь непонятно, один субъект «х» чёрно-белый или больше одного, а может вообще все. Поэтому утверждение «»х» — является пингвином, следовательно, является чёрно-белым», берётся в скобки и перед скобками используется символ «∀» с переменной «х» под ним — которые вместе и будут универсальным квантором.
Универсальный квантор переводится как: «Для всех «х» истинно, что …». Теперь утверждение «х — является пингвином, следовательно, является чёрно-белым» с универсальным квантором перед ним, расшифровывается так: «Для всех «х» истинно, что «х» — является пингвином, следовательно, является чёрно-белым». Это означает, что чем бы ни был объект во вселенной, если этот объект пингвин — он является чёрно-белым. Полная запись будет выглядеть так:
Экзистенциальный квантор (квантор существования) обозначается символом — «∃» с указанием переменной под ним. Возьмём утверждение «Некоторые пингвины серые». Как и в прошлый раз, выражение «»x» — является пингвином и «х» — является серым» возносим в скобки и ставим перед ними квантор, в этом случае экзистенциальный с указанной переменной. «»x» — является пингвином и «х» — является серым» записывается так: P(х) ∧ C(х), где P(х): х — пингвин; C(х): x — серый.
Экзистенциальный квантор можно перевести так: «Есть такой «х», для которого будет истинно, что …». Подразумевается, что есть как минимум один «х», для которого выполняются условия выражения. Если вам говорят, что ДНК не существует, достаточно показать одну молекулу дезоксирибонуклеиновой кислоты для опровержения этого утверждения. Также и с кванторами, если существует хотя бы один серый пингвин, то утверждение об отсутствии серых пингвинов будет ложно. Полная запись экзистенциального квантора для выражения «Есть такой «х», для которого будет истинно, что «x» — является пингвином и «х» — является серым», будет выглядеть так:
6 | Заключение
Примечательно, что есть возможность перевода одного вида квантора в другой. Возьмём утверждение «Все пингвины не являются серыми». Для универсального квантора текстовая запись будет такая: «Для всех «х», будет истинным утверждение о том, что если «х» — является пингвином, то «х» — не является серым объектом». Но утверждение изменяется и для экзистенциального квантора, используя знак отрицания: «Нет такого «х», для которого бы было истинным утверждение о том, что «x»— является пингвином и «х»— является серым».
В середине XIX века, Готлоб Фреге дополнил логику Аристотеля двумя этими операциями, которые позже сформировались в отдельную дисциплину — предикатную логику. С введением в логику экзистенциального квантора (после универсального) — предикатная логика, в основе своей, завершилась как система…
Источники:
1 — Аристотель: «Органон» — «Первая аналитика» и «Вторая аналитика»;
2 — Аристотель: «Риторика»;
3 — Готлоб Фреге: «Исчисление понятий»;
4 — «Monatshefte für Mathematik und Physik» 1931 г.: Курт Гёдель «О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах»;
5 — The Early Mathematical Manuscripts of Leibniz;
6 — Мельников Сергей: «Введение в философию Аристотеля»;
7 — Гильмутдинова Нина: «Логика и теория аргументации»;
ПРЕДИКАТ (в логике)
Смотреть что такое «ПРЕДИКАТ (в логике)» в других словарях:
ПРЕДИКАТ — (от лат. praedicatum сказанное) языковое выражение, обозначающее к. л. свойство или отношение. П., указывающий на свойство отдельного предмета (напр., «зеленый», «теплый»), называется одноместным. П., обозначающий отношение, называется… … Философская энциклопедия
ПРЕДИКАТ — (лат.). Сказуемое в предложении; то, что говорится о предмете. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. ПРЕДИКАТ 1) сказуемое; 2) титул, почетное звание. Словарь иностранных слов, вошедших в состав русского… … Словарь иностранных слов русского языка
Предикат (свойство отд. предмета) — Предикат (от позднелат. praedicatum сказанное), то же, что свойство; в узком смысле свойство отдельного предмета, например «быть человеком», в широком смысле свойство пары, тройки, вообще n ки предметов, например «быть родственником». П. в… … Большая советская энциклопедия
ПРЕДИКАТ — (от лат. praedicatum сказуемое) в узком смысле то же, что свойство; в широком смысле отношение, т. е. свойство нескольких предметов. В логике пропозициональная функция, т. е. выражение с неопределенными терминами (переменными), при выборе… … Большой Энциклопедический словарь
ПРЕДИКАТ — ПРЕДИКАТ, предиката, муж. (лат. praedicatum сказуемое) (научн.). 1. В логике понятие, определяющее предмет суждения субъект и раскрывающее его содержание (филос.). 2. То же, что сказуемое (грам.). Толковый словарь Ушакова. Д.Н. Ушаков. 1935 1940 … Толковый словарь Ушакова
ПРЕДИКАТ — ПРЕДИКАТ, а, муж. 1. В логике: понятие, определяющее предмет суждения (субъект). 2. В грамматике: член предложения, обозначающий отнесённый ко времени признак (действие или состояние). | прил. предикатный, ая, ое и предикативный, ая, ое (ко 2… … Толковый словарь Ожегова
Предикат (лингвистика) — У этого термина существуют и другие значения, см. Предикат. В Викисловаре есть статья «предикат» Предикат … Википедия
Предикат — I Предикат (от позднелат. praedicatum сказанное) то же, что свойство; в узком смысле свойство отдельного предмета, например «быть человеком», в широком смысле свойство пары, тройки, вообще n ки предметов, например «быть родственником». П … Большая советская энциклопедия
предикат — (от лат. praedicatum сказанное) языковое выражение, обозначающее какое то свойство или отношение. П., указывающий на свойство отдельного предмета (напр., быть зеленым ), называется одноместным. П., обозначающий отношение, называется двухместным,… … Словарь терминов логики
Логика предикатов
Понятие «предикат» обобщает понятие «высказывание». Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.
Возьмём высказывание: « расстояние от Иркутска до Москвы 5 тысяч километров ». Вместо него мы можем записать предикат « расстояние » (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов « Иркутск », « Москва » и « 5 тысяч километров ».
Язык логики высказываний не вполне подходит для выражения логических рассуждений, проводимых людьми, более удобен для этого язык логики предикатов.
Это рассуждение на языке логики высказываний можно записать тремя отдельными высказываниями. Однако никакой связи между ними установить не удастся. На языке логики предикатов эти предложения можно выразить с помощью двух предикатов: « быть человеком » и « быть смертным ». Первое предложение устанавливает связь между этими предикатами.
Перейдём теперь к формальному изложению логики предикатов.
Язык логики предикатов
«Предикатные формулы» обобщают понятие пропозициональной формулы, определённое в части 2.
3.1 Является ли » x формулой?
Как и в логике высказываний можно доказать, что множество формул замкнуто относительно правил построения. Теоремы возможности и единственности разбора подобны соответствующим теоремам для пропозициональных формул.
Свободные и связанные переменные
Множество свободных переменных * формулы F определяется рекурсивно, следующим образом:
Представление предложений русского языка предикатными формулами
Перед тем как мы продолжим изучение синтаксиса логики предикатов, полезно потренироваться в переводе предложений с русского языка в язык предикатных формул. *
В каждой из следующих задач представьте данное предложение русского языка предикатной формулой.
3.5 Все простые числа больше чем x.
Ответ: » y ( P ( y ) Й Q ( x, y )).
3.6 Существует простое число, которое меньше чем 10.
3.9 Существует бесконечно много простых чисел.
Подстановка
3.10 Найдите результат подстановки константы a вместо x в формулу из задачи 3.4.
3.12 Терм, не содержащий ни одной связанной переменной формулы F, является подстановочным в F для любой переменной.
Семантика
Выполнимость
Логическое следование
Выводы в логике предикатов
В логике предикатов вывод определяется так же, как и в исчислении высказываний и секвенции имеют тот же синтаксис. Аксиомы тоже определяются так же, как в логике высказываний. Все правила вывода логики высказываний – правила введения и удаления для пропозициональных связок, правила противоречия и сведения к противоречию – включены в множество правил вывода логики предикатов, с метапеременными для формул понимаемыми теперь как предикатные формулы. В дополнение, есть четыре новых правил вывода: правила введения и удаления для кванторов.
Правила для кванторов всеобщности
|
| ||||||||
| где v не является свободной | где t является | ||||||||
| переменной для любой формулы в G | подстановочным для v в F(v) |
В каждой из следующих задач выведите данную формулу из пустого множества посылок.
3.19 ( P ( a ) & » x ( P ( x ) Й Q ( x ))) Й Q ( a ).
3.20 » xy P ( x, y ) Й » x P ( x, x ).
Правила для кванторов существования
В каждой из следующих задач выведите данную формулу из пустого множества посылок.
Корректность и полнота логики предикатов
Множество правил вывода для логики предикатов обладает свойством корректности и полноты подобно свойствам пропозициональных выводов.
Полнота логики предикатов для случая счётного G и для другого множества правил вывода была доказана Куртом Гёделем в 1930 году.
Функциональные символы и равенство: синтаксис
Логика предикатов, определённая выше немного более ограничена, чем что обыкновенно называется «логикой первого порядка», и наша следующая цель – удалить эти ограничения. Во-первых, мы обобщим понятие терма. В дополнение к объектным константам и объектным переменным, мы разрешим построение термов с использованием символов для функций, «функциональных констант». Во-вторых, мы добавим к языку знак равенства, и уравнения будут включены как новый тип атомарных формул.
Наше наиболее общее понятие сигнатуры определяется следующим образом.
Функциональные символы и равенство: семантика
Выводы в логике первого порядка
Определение вывода в логике предикатов с функциональными константами и равенством включает новый тип аксиом и два новых правила вывода. Правила, как и раньше, содержат метапеременные, служащие для обозначения формул и термов.
Для каждой из следующих формул найдите вывод из пустого множества посылок.
3.27 x = y Й f ( x, y ) = f ( y, x ).
Теории первого порядка
Однако, добавление правил вывода для кванторов второго порядка ведёт к формальной системе которая корректна, но не полна.
Пример: Теория линейного порядка
Арифметика первого порядка
Интерпретация (7) является моделью этой теории. Арифметика первого порядка имеет также другие модели, и некоторые из них совсем не похожи на систему натуральных чисел (задача 3.40).
В каждой из следующих задач найдите доказательство данной формулы в арифметике первого порядка.
Нестандартные модели арифметики
3.38 Модель арифметики первого порядка (7) стандартна.
3.39 G непротиворечива.
3.40 Арифметика первого порядка имеет нестандартную модель.
Существование нестандартных моделей арифметики следует из теоремы Сколема (1920), который обобщил раннюю работу Леопольда Лёвенхейма (1915). Возможность таких моделей резко контрастирует с результатом задачи 1.41. Разница связана с тем, что язык арифметики первого порядка является слишком ограниченным для выражения аксиомы индукции. «Арифметика второго порядка», в которой схема индукции заменяется по аксиоме (8), не имеет нестандартных моделей.