ГЛОССАРИЙ

–А–

Алфавит исчисления высказываний

Алфавит исчисления высказываний состоит из символов трех категорий:

· Символы первой категории – переменные высказывания x, y, z, … ,x₁, x₂, …;

· Символы второй категории – логические связки – дизъюнкция, конъюнкция, импликация, отрицание;

· Символы третьей категории – скобки.

–Б–

Биекция

Отображение f, которое одновременно является сюръекцией и инъекцией называется биекцией (взаимно однозначное соответствие).

Бинарная операция

Бинарной операцией, заданной на множествах A и B, называется операция, заданная на множестве пар (a,b), где a – элемент A, b – элемент B.

Бинарное отношение

Говорят, что на множестве M задано бинарное отношение φ, если в M² выделено произвольное подмножество R_φ, т.е. каждый элемент a находится в отношении φ к элементу b в том и только в том случае, когда пара (a,b) принадлежит R_φ.

–В–

Взаимно обратные теоремы

Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу теоремами. Теоремы xE (P(x)Q(x)) и xE (Q(x)P(x)) взаимно обратные. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

Взаимно однозначное соответствие

См. биекция.

Взаимно противоположные теоремы

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

Вывод

Выводом из конечной совокупности формул H называется всякая конечная последовательность формул B₁, B₂, …, B_k, всякий член которой удовлетворяет одному из следующих трех условий:

· является одной из формул совокупности H;

· является доказуемой формулой;

· получается по правилу заключения из двух любых предшествующих членов этой последовательности.

Выполнимая формула

Формулу A называют выполнимой, если она принимает значение «1» хотя бы при одном наборе значений входящих в нее переменных и не является тождественно истинной.

Высказывание

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

–Д–

Двухместный предикат

Двухместным предикатом P(x,y) называется функция двух переменных x и y, определенная на множестве M=M₁M₂, xM₁, yM₂, и принимающая значения из множества {1,0}.

Дизъюнкция высказываний

Дизъюнкцией двух высказываний x и y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y истинно, и ложным, если они оба ложны. Высказывания x и y называются членами дизъюнкции. Обозначение xy.

Дизъюнкция предикатов

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)Q(x), который принимает значение «0» при тех и только тех значениях xM, при которых каждый из предикатов принимает значения «0» и значение «1» во всех остальных случаях. Областью истинности предиката P(x)Q(x) является объединение областей истинности предикатов P и Q, т.е. I_PI_Q.

Доказуемая формула

· Всякая аксиома является доказуемой формулой;

· Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной произвольной формулы, есть доказуемая формула;

· Формула B, полученная из доказуемых формул A и Aпутем применения правил заключения, является доказуемой формулой;

· Никакая другая формула исчисления высказываний не является доказуемой.

–Е–

Единичное высказывание

Пусть P(x) – предикат, определенный на множестве M. Пусть aM. Подставим его вместо x в предикат P(x). Получим высказывание P(a), которое называется единичным высказыванием.

–И–

Импликация высказываний

Импликацией двух высказываний x, y называется новое высказывание, которое считается ложным, когда x – истинно, а y – ложно, и истинным во всех остальных случаях. Обозначение x→y. Высказывание x называется условием (посылкой), высказывание y – следствием (заключением).

Импликация предикатов

Импликацией предикатов P(x) и Q(x) называется новый предикат P(x)Q(x), который принимает значение «0» при тех и только тех значениях xM, при которых одновременно P(x) принимает значение «1», а Q(x) – значение «0», и принимает значение «1» во всех остальных случаях. Областью истинности предиката P(x)Q(x) является множество I_PQ=CI_PI_Q.

Инъекция

Если для двух различных элементов x₁ и x₂ множества X их образы y₁=f(x₁), y₂=f(x₂) также различны, то отображение f называется инъекцией.

Исчисление высказываний

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

–К–

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

Пусть P(x) – предикат, определенный на множестве M. Под выражением xP(x) понимают высказывание, истинное, когда P(x) истинно для каждого элемента xM и ложное в противном случае. Это высказывание не зависит от x. Соответствующее ему словесное выражение «для всякого x P(x) истинно». Символ называется квантором всеобщности.

Переменную x в предикате P(x) называют свободной (ей можно придавать различные значения из M), в высказывании xP(x) переменную x называют связанной квантором всеобщности.

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

Пусть P(x) – предикат, определенный на множестве M. Под выражением xP(x) понимают высказывание, которое является истинным, если существует элемент xM, для которого P(x) истинно и ложным в противном случае. Это высказывание не зависит от x. Соответствующее ему словесное выражение «существует x, при котором P(x) истинно». Символ называется квантором существования.

Конечное множество

Множество, имеющее конечное число элементов, называется конечным множеством.

Конъюнкция высказываний

Конъюнкцией двух высказываний x и y называется новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным, если хотя бы одно из них ложно. Высказывания x и y называются членами конъюнкции. Обозначение xy.

Конъюнкция предикатов

Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)Q(x), который принимает значения «1» при тех и только тех значениях xM, при которых каждый из предикатов принимает значение «1» и принимает значение «0» во всех остальных случаях. Областью истинности предиката P(x)Q(x) является пересечение областей истинности предикатов P и Q, т.е. I_PI_Q.

–Л–

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

Логика предикатов разбивает элементарное высказывание на субъект (подлежащее или дополнение) и объект (сказуемое или определение). Субъект – это то, о чем утверждается в высказывании, предикат – это то, что утверждается о субъекте.

Логические значения высказываний

Логическими значениями высказываний являются «истина» и «ложь». Обозначения: истинное значение высказывания – буквой «и» или цифрой «1», ложное значение высказывания – буквой «л» или цифрой «0».

Логические операции над высказываниями

Логическими операциями над высказываниями являются отрицание, конъюнкция, дтзъюнкция, импликация и эквиваленция высказываний.

–М–

Метод математической индукции

Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность одноместного предиката A(n) для всех натуральных n, то:

· Проверяют истинность высказывания A(1);

· Предположив истинность высказывания A(k) пытаются доказать, что A(k+1) истинно.

Если это удается доказать, причем доказательство остается справедливым для каждого натурального значения k, то в соответствии с принципом математической индукции предикат A(n) признается истинным для всех значений n.

Метод от противного

При доказательстве теорем методом от противного предполагается , что теорема xE (P(x)Q(x)) неверна, т.е. существует такой объект x, что условие P(x) истинно, а заключение Q(x) – ложно. Если из этих предположений приходят к противоречивому утверждению, то делают вывод о том, что предположение неверно, и верна теорема xE (P(x)Q(x)).

Множество истинности предиката

Множество всех элементов xM, при которых при которых предикат P(x) принимает значение «1», называется множеством истинности предиката P(x) и обозначается I_p={x: xM, P(x)=1}.

Мощность конечного множества

Мощностью конечного множества A называется количество его элементов. Обозначение m(A).

–Н–

Независимая аксиома

Аксиома называется независимой от всех остальных аксиом, если она не может быть выведена из всех остальных аксиом.

Независимая система аксиом

Система аксиом исчисления называется независимой, если каждая аксиома системы независима.

Необходимое и достаточное условия

Рассмотрим теорему xE (P(x)Q(x)). Предикат P(x)Q(x) истинен для всех xE в том и только в том случае, когда I_PI_Q. При этом говорят, что предикат Q(x) логически следует из предиката P(x), и предикат Q(x) называют необходимым условием для предиката P(x), а предикат P(x) – достаточным условием для предиката Q(x).

Непротиворечивое аксиоматическое исчисление

Аксиоматическое исчисление называется непротиворечивым, если в нем не существует такая формула , что доказуема и доказуема . Если такая формула существует, то аксиоматическое исчисление называется противоречивым.

Непротиворечивое логическое исчисление

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

Несчетное множество

Бесконечное множество, не являющееся счетным, называется несчетным множеством.

–О–

Объединение множеств

Объединением множеств A и B называется множество C, состоящее из элементов, принадлежащих хотя бы одному из множеств A или B.

Одноместный предикат

Одноместным предикатом P(x) называется произвольная функция переменной x, определенная на множестве M и принимающая значения из множества {1,0}. Множество M, на котором определен предикат P(x) называется областью определения предиката.

Отношение эквивалентности

Отношение φ называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности.

Отрицание высказывания

Отрицанием высказывания x называется новое высказывание, которое является истинным, если x ложно и ложным, если x истинно.

Отрицание предиката

Отрицанием предиката называется новый предикат , который принимает значение «1» при всех значениях , при которых предикат принимает значение «0», и принимает значение «0» при тех значениях , при которых предикат принимает значение «1». Область истинности предиката .

–П–

Пересечение множеств

Пересечением множеств A и B называется множество C, состоящее из элементов, принадлежащих как множеству A, так и множеству B.

Подмножество

Если множество A есть часть множества B, то множество A называют подмножеством множества B. Обозначение .

Подформула формулы исчисления высказываний

· Подформулой элементарной формулы является только она сама;

· Если формула имеет вид , то ее подформулами являются она сама, формула и все подформулы формулы .

· Если формула имеет вид , где под символом понимается любой из трех , то ее подформулами являются она сама, формулы и , все подформулы формул и .

Полное в узком смысле аксиоматическое исчисление

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

Полное в широком смысле исчисление высказываний

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

Полный прообраз множества

Пусть B подмножество множества Y. Совокупность всех тех элементов из X, образы которых принадлежат B, называется полным прообразом множества B и обозначается f^-1(B).

Правило заключения

Если формулы A и A®B доказуемы в исчислении высказываний, то формула B также доказуема.

Правило контрпозиции

Если доказуема формула A®B, то доказуема формула .

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

Если A – доказуемая формула, x₁, x₂,…,x_n – переменные, B₁, B₂,…,B_n – любые формулы исчисления высказываний. Тогда результат одновременной подстановки в A вместо x₁, x₂,…,x_n формул B₁, B₂,…,B_n соответственно, является доказуемой формулой.

Правило подстановки

Если формула A доказуема в исчислении высказываний, x – переменная, B – произвольная формула исчисления высказываний, то формула, полученная в результате замены в формуле A переменной x всюду, где она входит, формулой B, является также доказуемой формулой.

Операция замены в формуле A переменной x формулой B называется подстановкой.

Правило силлогизма

Если доказуемы формулы A®B и B®C, то доказуема формула A®C.

Правило сложного заключения

Пусть даны формулы A₁, A₂, …, A_n, A₁®(A₂®(A₃®(…(A_n®L)…))). Если все вышеуказанные формулы доказуемы, то и формула L доказуема.

Принцип математической индукции

Предикат A(n) считается истинным для всех натуральных значений переменной, если выполнены следующие условия:

· A(n) истинен при n=1;

· Для kN из допущения, что A(n) истинно для n=k, вытекает, что оно истинно и для n=k+1.

Этот принцип называется принципом математической индукции.

Допущение, что A(n) истинно для n=k называют индуктивным допущением или индуктивным предположением.

Простое высказывание

См. элементарное высказывание.

Противоречие

См. тождественно ложная формула.

Пустое множество

Множество, не содержащее ни одного элемента, называется пустым.

–Р–

Равномощные множества

См. эквивалентные множества.

Равносильные формулы алгебры логики

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

Равные множества

Множества называются равными, если они состоят из одних и тех же элементов.

Разбиение множества на классы

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

Разность множеств

Разностью множеств A B называется множество C, состоящее из тех элементов множества A, которые не содержатся в множестве B.

–С–

Свойство антисимметричности отношения

Отношение φ обладает свойством антисимметричности, если из того, что элемент a связан с элементом b отношением φ и элемент b связан с элементом a отношением φ, следует, что a=b.

Свойство рефлексивности отношения

Отношение φ обладает свойством рефлексивности, если элемент a связан с элементом a отношением φ.

Свойство симметричности отношения

Отношение φ обладает свойством симметричности, если из того, что элемент a связан с элементом b отношением φ, следует, что элемент b связан с элементом a отношением φ.

Свойство транзитивности отношения

Отношение φ обладает свойством транзитивности, если из того, что элемент a связан с элементом b отношением φ и элемент b связан с элементом c отношением φ, следует, что элемент a связан с элементом с отношением φ.

Связка Лукасевича

Связкой Лукасевича называется конъюнкция отрицания. Обозначение x↓y= (“ни x, ни y”).

Связка Шеффера

Связкой Шеффера называется дизъюнкция отрицания. Обозначение x│y= (“x несовместно с y”).

Сложное высказывание

См. составное высказывание.

Собственные подмножества

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

Составное высказывание

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

Счетное множество

Множество эквивалентное множеству натуральных чисел называется счетным множеством.

–Т–

Тавтология

См. тождественно истинная формула.

Таблица истинности

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

Тождественно истинная формула

Формула A называется тождественно истинной (тавтологией), если она принимает значение «1» при всех значениях входящих в нее переменных.

Тождественно истинный предикат

Предикат P(x), определенный на множестве M, называется тождественно истинным, если его множество истинности I_P=M.

Тождественно ложная формула

Формула A называется тождественно ложной (противоречие), если она принимает значение «0» при всех значениях входящих в нее переменных.

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

Предикат P(x), определенный на множестве M, называется тождественно ложным, если его множество истинности I_P=Ø.

–Ф–

Формула алгебры логики

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

Формула, выводимая из совокупности формул

Пусть дана конечная совокупность формул H={A₁,A₂,…,A_n}:

· Всякая формула A_iÎH является формулой, выводимой из H;

· Всякая доказуемая формула выводима из H;

· Если формулы C и C®B выводимы из совокупности H, то формула B также выводима из H.

Формула исчисления высказываний

Формулы исчисления высказываний представляют собой последовательности символов алфавита исчисления высказываний, удовлетворяющих следующим условиям:

· Всякая переменная высказывания является формулой;

· Если и – формулы, то слова – формулы;

· Никакая другая строка символов не является формулой.

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

–Э–

Эквивалентные множества

Два множества, между которыми можно установить взаимно однозначное соответствие, называются эквивалентными (равномощными).

Эквиваленция высказываний

Эквиваленцией (эквивалентностью) двух высказываний x, y называется новое высказывание, которое считается истинным, когда оба высказывания x, y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях. Высказывания x, y называются членами эквиваленции. Обозначение x↔y.

Элементарная формула исчисления высказываний

Переменные высказывания называются элементарными формулами исчисления высказываний.

Элементарное высказывание

Высказывание называется элементарным (простым), если оно представляет собой одно утверждение.