Вопросы МатЛогика
.docx№18 Множество истинности предиката
Множеством истинности предиката , заданного на множествах , называется совокупность всех упорядоченных n-систем , в которых , таких, что данный предикат обращается в истинное высказывание при подстановке . Это множество будем обозначать .
№19 Равносильность и следование предикатов
Два n-местных предиката и , заданных над одними и теми же множествами , называются равносильными, если набор предметов (элементов) превращает первый предикат в истинное высказывание в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание .
Предикаты и равносильны тогда и только тогда, когда их множества истинности совпадают. .
Предикат , заданный над множествами , называется следствием предиката , заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат . Предикат является следствием предиката тогда и только тогда, когда . Утверждение о том, что предикат является следствием предиката , будем символически записывать так: .
№20 Логические операции над предикатами
Над предикатами можно проделывать те же самые логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность.
Отрицанием n-местного предиката , определенного на множествах , называется новый n-местный предикат, определенный на тех же множествах, обозначаемый (читается: "неверно, что , который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание.
Конъюнкцией "n-местного предиката , определенного на множествах , и m-местного предиката , определенного на множествах , называется новый (n+m)-местный предикат, определенный на множествах , обозначаемый (читается " и "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.
Дизъюнкцией n-местного предиката , определенного на множествах , и m-местного предиката , определенного на множествах , называется новый (n+m)-местный предикат, определенный на множествах и , обозначаемый
(читается " или "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов.
Импликация определяется как такой предикат, что для любых предметов
и
высказывание является импликацией высказываний и . Аналогично определяется эквивалентность двух предикатов.
№21 Квантор общности одноместного предиката
Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату , определенному на множестве , сопоставляется высказывание, обозначаемое (читается: "для всякого [значения] [истинное высказывание]"), которое истинно в том и только в том случае, когда предикат тождественно истинен, и ложно в противном случае,
При чтении высказывания слова в квадратных скобках могут опускаться. Высказывание называется универсальным высказыванием для предиката . Символ происходит от первой буквы англ. all — "все". Сам символ также называют квантором общности по переменной .
№22 Квантор существования одноместного предиката
Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату , определенному на множестве , ставится в соответствие высказывание, обозначаемое (читается: "существует [значение] , такое, что [истинное высказывание]"), которое ложно в том и только в том случае, когда тождественно ложен, и истинно в противном случае, т.е.
При чтении высказывания слова в квадратных скобках могут опускаться. Высказывание называется экзистенциальным высказыванием для предиката . Символ происходит от первой буквы англ. exist — "существовать". Сам символ также называют квантором существования по переменной .
№23 Квантор общности n-местного предиката
Операцией связывания квантором общности по переменной называется правило, по которому каждому n-местному предикату , определенному на множествах , ставится в соответствие новый (n-1)-местный предикат, обозначаемый (читается: "для всех , который для любых предметов превращается в высказывание , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве тождественно истинен, и ложное в противном случае.
№24 Квантор существования n-местного предиката
Операцией связывания квантором существования по переменной называется правило, по которому каждому n-местному предикату , определенному на множествах , ставится в соответствие новый (n-1)-местный предикат, обозначаемый (читается: "существует такой что , который для любых предметов превращается в высказывание , ложное в том и только в том случае, когда одноместный предикат , определенный на множестве тождественно ложен, и истинное в противном случае
№25 Формулы логики предикатов
Сначала задается алфавит символов, из которых будут составляться формулы:
– предметные переменные: ; – нульместные предикатные переменные: ; – n-местные предикатные переменные с указанием числа свободных мест в них:
– символы логических операций: ; – кванторы: ; – вспомогательные символы: — скобки; — запятая.
(формулы логики предикатов).
1) Каждая нульместная предикатная переменная есть формула;
2) если — n-местная предикатная переменная, то есть формула, в которой все предметные переменные свободны;
3) если — формула, то — также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными) в ;
4) если — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения {Лог.операции конъюнкции, дизъюнкции и тд над F1 и F2} также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;
5) если — формула и — предметная переменная, входящая в свободно, то выражения и также являются формулами, в которых переменная связанная, а все остальные предметные переменные, входящие в формулу свободно или связанно, остаются и в новых формулах соответственно такими же;
6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.
Формулы, определенные в пунктах 1 и 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.
№26 Тавтологии логики предикатов
Теорема Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов.
№27
Две формулы, и логики предикатов называются равносильными на множестве , если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на , формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: .
(законы де Моргана для кванторов). Следующие формулы логики предикатов являются тавтологиями:
а) ; б) .
Следствие Следующие формулы логики предикатов являются тавтологиями:
а) ; б) .
Дистрибутивность (законы пронесения кванторов через конъюнкцию и дизъюнкцию). Следующие формулы логики предикатов являются тавтологиями:
а) ; б) ; в) ; г) .
№28
(законы пронесения кванторов через импликацию). Следующие формулы логики предикатов являются тавтологиями:
а) ; б) ; в) ; г) .
(законы удаления квантора общности и введения квантора существования). Следующие формулы логики предикатов являются тавтологиями:
а) ; б) .
№29 Приведенная форма, предваренная нормальная форма
Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции , причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.
Теорема Для каждой формулы логики предикатов существует приведенная форма
Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида , где есть один из кванторов или , причем формула не содержит кванторов и является приведенной формулой. (Заметим, что кванторы в формуле могут отсутствовать вовсе.)
Теорема Для каждой формулы логики предикатов существует предваренная нормальная форма.
№30 Машина Тьюринга
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
-
Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
-
Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
-
Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
-
Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
-
Передвигаться на одну ячейку влево или вправо.
-
Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния)