Программируемые логические матрицы

⇐ ПредыдущаяСтр 16 из 27Следующая ⇒

Рассмотрим схему, состоящую из р входов z 1, ..., zpи q выходов g 1, …, g q (рис. 6.28), в которой значения выходов определяются матрицей соединений (cih), 1 ≤ i ≤ p , 1 ≤ y ≤ q , cih∈ {0, 1} по следующим правилам Таким образом, где , а остальные cih= 0. Полученная схема называется решеткой с р входами и q выходами элементов &, которая определяется матрицей соединений (cih).

Рис. 6.28

Программируемой логической матрицей (ПЛМ) называется изображенная на рис. 6.29 схема, получающаяся соединением решетки А с 2n входами и k выходами, определяемой матрицей соединений (aih), и решетки В с k входами и т выходами, определяемой матрицей соединений (bhj).

Рис. 6.29

Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных x 1, x 2, …, xn. Поскольку к каждому входу xiприсоединен инвертор , на 2n входов решетки А подаются значения переменных

После прохождения решетки A h -й выход принимает значение функции , а последующей операции инвертирования соответствует функция

Полученные k значений (1 ≤ h ≤ k ) подаются на входы решетки B , после прохождения которой на выходе j образуется значение функции

В заключение после инвертирования по законам де Моргана на выходе j получаем значение функции , j = 1, …, m . Функции fiсоответствует дизъюнкция конъюнктов (определяемых формулами ) таких, что bhj= 1.

Таким образом, при соответствующем выборе матриц (aih) и (bhj) можно одновременно реализовать m произвольных ДНФ, содержащих не более k различных конъюнктов переменных от x 1, x 2, …, xn.

Цит. по: Элементы дискретной математики: учебник /
С.В. Судоплатов, Е.В. Овчинникова. — М.: ИНФРА-М;
Новосибирск: НГТУ, 2003. — С. 172–210. — (Серия «Высшее образование»).

Тема 2. Логика предикатов

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

В текстах естественного языка часто встречаются повествовательные предложения, не являющиеся высказываниями, например эти предложения могут иметь неопределенные параметры. Например, такие предложения, как «У девочки красивая коса», «Число х — простое», «х + у = z ».

Если в такие предложения вместо параметров (переменных) поставить конкретную девочку и конкретные числа х, у, z , то получим высказывания, которые станут истинными или ложными, например «У Веры красивая коса», «Число 17 простое» или «7 + 8 = 9» и т. п.

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

Определение 9.1 (предиката ). Функция Р (х 1, ..., хп), определенная на некотором множестве М и принимающая одно из двух значений: И (истина) или Л (ложь):

P : M → {И, Л},

называется п-местным предикатом.

Множество М часто задано по умолчанию обычным математическим контекстом.

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

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

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

Пример 9. 1. Пусть Р (1)(х ) — предикат «х делится на два»; Q (1)( x ) — предикат «х делится на три».

Тогда выражение

Р (1)(х ) & Q (1)( x )

означает: «х делится на два и х делится на три», т. е, это выражение определяет предикат «х делится на шесть».

Аналогичным образом можно использовать все логические связки логики высказываний:

&, ∨ , ⌉ , ⇒ , ~.

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

Определение 9.2 (квантора общности ). Пусть Р (х ) — некоторый предикат, принимающий значения И или Л для каждого х множества М. Под выражением ( ∀ x ) P ( x ) будем подразумевать высказывание истинное, когда Р (х ) истинно для каждого элемента х из множества М, и ложное — в противном случае. Читается оно: «для всех х Р (х )». Этот новый предикат уже не зависит от х, т. е. является высказыванием. Символ ∀ называется квантором общности, а переменная х называется связанной (квантором). Несвязанные квантором переменные обычно называются свободными.

Определение 9.3 (квантора существования ). Пусть Р (х ) — некоторый предикат. Под выражением ( ∃ х )Р (х ) будем понимать высказывание истинное, когда существует элемент множества М, для которого Р (х ) истинно, и ложное — в противном случае. Читается это выражение так: «существует х такое, что Р (х )», или «существует х, для которого Р (х )». Полученный новый предикат тоже не зависит от х и является высказыванием. Символ ∃ называется квантором существования, а переменная х — связанной (квантором). Несвязанные квантором переменные обычно называют свободными.

Пример 9. 2. Вернемся к примеру 9.1 о делимости на 3 и на 2. Тогда на множестве натуральных чисел предикат

(∃ х ) Р (1)(х ) & Q (1)( x )) —

истинное высказывание, а предикат

(∀ х ) Р (1)(х ) & Q (1)( x )) —

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

Замечание 9.1. Операцию связывания кванторами можно применять и к предикатам от большего числа переменных. При этом те переменные в предикате, на которые действует какой-либо квантор, будут связанными, а все остальные — свободными.

Формулы логики предикатов

Теперь определим понятие формулы логики предикатов.

Определение 9.4. Алфавит логики предикатов содержит следующие символы.

1. Символы предметных переменных:

x 1, x 2, …

2. Символы предикатов:

где t = 0, 1, …

3. Логические символы:

⌉, &, ∨ , ⇒ , ~.

4. Символы кванторов:

∃ , ∀ .

5. Скобка и запятая:

), (.

Отличие алфавита логики высказываний от алфавита логики предикатов в наличии п. 1 и 4; кроме того, п. 2 здесь шире (в алфавите логики высказываний t = 0); в п. 5 появилась «запятая».

Чтобы избежать нагромождения индексов, часто символы переменных будем обозначать через x , y, z, а символы предикатов через Р, Q , R , S и т. д.

Определение 9.5. Слово в алфавите логики предикатов называется формулой или правильно построенным словом, если оно удовлетворяет следующему рекурсивному определению.

1. Если — символ предиката; — символы предметных переменных, необязательно различные, то — формула. Такая формула называется атомарной. Все предметные переменные атомарных формул свободные, связанных переменных нет.

2. Пусть а — формула. Тогда ⌉ а — тоже формула. Свободные и связанные переменные формулы ⌉ а — соответственно свободные и связанные переменные формулы а.

3. Пусть а и b — формулы, причем нет таких переменных, которые были бы связанными в одной формуле и свободными в другой. Тогда

(а ∨ b ), ( a & b ), (а ⇒ b ), (а ~ b )

есть формулы, в которых свободные переменные формул а и b остаются свободными, связанные остаются связанными.

4. Пусть а — формула, содержащая свободную переменную х. Тогда ( ∀ x )а, ( ∃ х )а — тоже формулы. Переменная x в них — связанная. Остальные переменные, которые в формуле а свободны, остаются свободными и в этих формулах.

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

В формуле ( ∀ x )а формула а называется областью действия квантора ∀ , а в формуле ( ∃ х )а — областью действия квантора ∃ .

5. Других правил нет.

Замечание 9.2. По определению формулы никакая переменная не может быть одновременно свободной и связанной. Для оценки формулы на истинность и ложность требуется зафиксировать значения всех свободных предметных переменных, взяв их значения из множества допустимых значений.

Пример 9. 3. Рассмотрим предикат «Каждый водитель должен соблюдать правила».

Назовем параметры: «водитель», «правила». Первый параметр — связанная переменная, второй — свободная.

Зафиксируем вторую переменную: «правила дорожного движения». Если такой закон в РФ есть, то получаем «И», если нет, то «Л».

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

Определение 9.6. Интерпретацией называется пара I = á М , Ф ñ , состоящая из непустого множества М и соответствия Ф. При этом множество М задает область значений предметных переменных, а соответствие Ф сопоставляет каждой атомарной формуле Aj( x 1, ..., xt) конкретный t -местный предикат, заданный на М.

При заданной интерпретации считают, что предметные переменные пробегают множество М, а символы ⌉, &, ∨ , ⇒ , ~.и символы кванторов имеют обычный смысл.

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

Пример 9. 4. Пусть f ( x ) — произвольная фиксированная функция, заданная на отрезке [а, b ].

1. Рассмотрим интерпретацию I = á М , Ф1ñ , где М — множество действительных чисел; Ф1— соответствие, сопоставляющее формулам Р (х, δ ), Q ( x , ε ), R (ε ) их конкретные предикаты (характеристические функции):

Здесь х 0— фиксированный элемент отрезка [а, b ]; с — некоторое фиксированное действительное число. Тогда определение того, что записывается формулой

2. Рассмотрим интерпретацию I = á М , Ф2ñ , где М — множество действительных чисел; Ф2— соответствие, сопоставляющее формулам Р (х, δ ), S ( x , ε ), R (ε ) предикаты:

Здесь х 0— произвольный фиксированный элемент отрезка [а, b ]. Тогда определение о том, что функция f ( x ) непрерывна в точке х 0, записывается формулой

Здесь рассмотрен простой вариант определения формул логики предикатов. Для описания более серьезных языковых конструкций требуется расширение понятия формулы и использование еще понятия терма. Мир термов описывает предметную область интерпретации средствами классической математики. Для определения термов требуется расширить алфавит формальной теории. Кроме символов предметных переменных xiтребуется ввести еще символы констант ajи функциональные символы алгебраических операций над предметными переменными и над константами. Здесь число m = 0, 1, 2, ... называется арностью или числом мест операции. Терм определяется рекурсивно.

Определение 9.7. Всякая предметная переменная, или константа, является термом.

Правила преобразования формул логики предикатов

Пусть формулы f и g имеют одно и то же множество свободных переменных (в частности, пустое).

Определение 9.8. Формулы f и g равносильны в данной интерпретации I = á М , Ф ñ , если на любом наборе значений свободных переменных они принимают одинаковые значения, т. е. если формулы выражают в данной интерпретации один и тот же предикат.

Формулы f и g равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М. Формулы f и g равносильны в алгебре (логике) предикатов, если они равносильны во всех интерпретациях. Тогда будем писать: f ≡ g .

Пример 9. 6. Рассмотрим формулы:

Эти формулы равносильны на одноэлементном множестве. В самом деле, если область интерпретации — одноэлементное множество, то какой бы предикат ни взяли в качестве интерпретации на этом множестве, он принимает только значения И или Л.

В первом случае обе формулы принимают значение И, во втором — Л, и, следовательно, они равносильны на этом множестве.

С другой стороны, на двухэлементном множестве {а, b } эти формулы не равносильны.

Теперь рассмотрим правила перехода от одних формул к другим, им равносильным во всех интерпретациях.

Теорема 9.1 (правила булевой алгебры ). Для формул алгебры предикатов сохраняются все равносильности и правила равносильных преобразований алгебры высказываний.

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

Здесь формулы а, b , с являются предикатами. Рассмотрим произвольную интерпретацию I = á М , Ф ñ и зададим свободные переменные в формулах а, b , с конкретными значениями. Тогда эти формулы станут высказываниями со своими истинностными значениями, для которых закон дистрибутивности выполняется. Следовательно, в силу произвольности интерпретации, дистрибутивность будет выполняться в логике предикатов. Аналогично доказываются все равносильности из логики высказываний,

Теорема 9.2 (правило переноса квантора через отрицание ). Пусть а — формула, содержащая свободную переменную х. Тогда:

Теорема 9.3 (правило выноса квантора за скобки ). Пусть а (х ) содержит свободную переменную х, формула b не содержит переменной х и обе они удовлетворяют п. 3 определения 9.5, т.е. нет таких переменных, которые были бы связаны в одной формуле и свободны в другой. Тогда:

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

Теорема 9.4 (правило перестановки одноименных кванторов ).

Теорема 9.5 (правило переименования связанных переменных ). Заменяя связанную квантором переменную формулы а всюду в области действия квантора другой переменной, не входящей в эту формулу, получаем формулу, равносильную а.

Определение 9.9. Длиной формулы называется общее число входящих в нее символов предикатов (атомарных формул), логических символов и символов кванторов.

Пример 9. 7. Рассмотрим формулу

Эта формула имеет длину 5. Длину здесь составляют символы:

Определение 9.10. Формулы, в которых из логических символов имеются только символы &, ∨ , ⌉ (стандартный базис), причем символ ⌉ встречается только перед атомарными подформулами (тесное отрицание), называются приведенными.

Пример 9. 8. Рассмотрим формулы:

Первая является приведенной, вторая — нет. (Почему? ) В заключение укажем, до какой степени формулы можно упростить с помощью равносильностей.

Определение 9.11. Приведенная формула называется нормальной, если она содержит все символы кванторов впереди или кванторов вовсе нет.

Пример 9. 9. Формула является нормальной.

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

Теорема 9.6. Для любой формулы существует равносильная ей приведенная формула, для которой, в свою очередь, существует равносильная ей нормальная формула.

Пример 9. 10. Рассмотрим некоторую теорему из математического анализа.

Теорема Лагранжа о конечном приращении. Если функция f ( x ) непрерывна на отрезке [а, b ] и дифференцируема в интервале (а, b ), то существует точка с, с ∈ (а, b ), такая, что выполняется равенство f ( b ) – f ( a ) = f '( c )( b – а ).

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

Перейдем к формализации теоремы Лагранжа в рамках логики предикатов.

Шаг 1. Перечислим все предметы, о которых идет речь в теореме, и обозначим их предметными переменными. Всего в теореме четыре предмета — три числа а, b , с и одна функция f , или в стандартном обозначении f ( x ).

Шаг 2. Выделим в теореме простейшие части текста (смыслы) о предметах и формализуем их в виде атомарных формул. Получим:

P ( a , b , f ( x )) = «функция f ( x ) непрерывная на отрезке [а, b ]»;

Q ( a , b , f ( x )) = «функция f ( x ) дифференцируемая в интервале (а, b )»;

R (a, b, с ) = « с ∈ ( а , b )»;

S (a, b, с , f (x )) = «f (b ) – f (a )) = f '(c ) (b – а )».

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

⇐ Предыдущая 11 12 13 14 151617 18 19 20 Следующая ⇒