4. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста (1268165)
Текст из файла
Лекция: Конечнозначные функции.Элементарные k-значные функции. Способызадания k-значных функций: таблицы, формулы,1-я и 2-я формы, полиномы. Полнота. Теорема ополноте системы Поста. Функция Вебба.Лектор - доцент Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаКонечнозначные функцииПусть k ≥ 2 — целое число, Ek = {0, 1, . .
. , k − 1}.Функция f (x1 , . . . , xn ) называется k-значной, еслиf n : Ekn → Ek ,где n = 1, 2, . . ..Множество всех k-значных функций обозначим как Pk ,множество всех k-значных функций, зависящих от переменныхx1 , . . . , xn , обозначим как Pkn .При k = 2 функции называются функциями алгебры логики,или булевыми функциями, при k ≥ 3 — многозначнымифункциями.Аналогично двузначному случаю равенство многозначныхфункций (k ≥ 3) рассматривается с точностью донесущественных (фиктивных) переменных.Конечнозначные функцииСпособы заданияНормальные формыПолиномыСущественные и несущественные переменныеПеременная xi называется существенной для функцииf (x1 , .
. . , xn ) ∈ Pk , если найдутся такие элементыa1 , . . . , ai−1 , ai+1 , . . . , an ∈ Ek , чтоϕ(xi ) = f (a1 , . . . , ai−1 , xi , ai+1 , . . . , an ) 6= Const.Переменная xi является существенной, если все другиепеременные можно так определить, что полученная функцияодной переменной xi принимает хотя бы два различныхзначения.Переменная, не являющаяся существенной, называетсянесущественной, или фиктивной.Фиктивные переменные можно удалять и добавлять.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыРавенство и конгруэнтность функцийФункции f и g называются равными, если конечным числомудалений или добавлений несущественных переменных ихможно сделать совпадающими.Функции f и g называются конгруэнтными, если равные имфункции осуществляют одинаковые отображения, т.е.отличаются только именами переменных.Примеры.1.
Функции f1 (x) = 0 и f2 = 0 равны.2. Функции g (x) = x и h(y ) = y конгруэнтны.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПрименениеКонечнозначные функции могут применяться для построениямоделей решения прикладных задач, в которых можновыделить исходное множество, состоящее из конечного числаэлементов.Не столь широкое применение k-значных функций при k ≥ 3 посравнению с двузначными связано, в первую очередь, сфизической реализацией вычислительной техники надвузначной основе.Проводятся исследования, относящиеся к разработкефизических схем, реализованных на многозначных функциях;существуют промышленные цифровые устройства намногозначной основе.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаТаблицы значенийКак можно задавать k-значные функции?1.
Таблицы значений.Упорядочим все наборы множества Ekn в лексико-графическом,или алфавитном порядке (в алфавите 0, 1, . . . , k − 1),сопоставим каждому набору значение функции на нем.x100. . . xn−1xnf (x1 , . . . , xn−1 , xn )...00f (0, . . . , 0, 0)...01f (0, . . . , 0, 1)...0...0k −1f (0, . . . , 0, k − 1)...k − 1 ... k − 10f (k − 1, . . . , k − 1, 0)...k − 1 . . . k − 1 k − 2 f (k − 1, . . . , k − 1, k − 2)k − 1 . . .
k − 1 k − 1 f (k − 1, . . . , k − 1, k − 1)Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаЧисло k-значных функцийnТеорема 1. Пусть k ≥ 2. При n ≥ 1 верно |Pkn | = k k .Доказательство.Рассмотрим произвольную функцию f (x1 , . . . , xn ) ∈ Pkn .В ее таблице k n строк.В каждой строке вне зависимости от других строк — еезначение на этом наборе из k возможных значений.nОтсюда |Pkn | = k k .Конечнозначные функцииСпособы заданияНормальные формыЭлементарные функции2. Формулы.Элементарные k-значные функции (k ≥ 3).n = 0:константы 0, 1, . . . , k − 1.n = 1:xxx̄∼x−x001k −10112k −2 k −1...k −2 k −2 k −112k −1 k −1001x — тождественно x;x̄ = x + 1(mod k) — отрицание Поста x;∼ x = (k − 1) − x — отрицание Лукасевича x;−x = k − x(mod k) — минус x.ПолиномыПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЭлементарные функцииХарактеристические функции выделенного значения Ji (x),ji (x), i = 0, 1, .
. . , k − 1:k − 1, x = i;Ji (x) =0,x 6= i.1, x = i;ji (x) =0, x 6= i.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЭлементарные функцииn = 2:x + y (mod k), x − y (mod k), x · y (mod k) — сложение,вычитание иумножение по модулю k;x, x ≤ y ;min(x, y ) =— минимум из x и y ;y, x > y.x, x ≥ y ;max(x, y ) =— максимум из x и y ;y, x < y.x − y, x ≥ y;x −̇y =— усеченная разность;0,x < y.k − 1,x ≤ y;x →y =— импликация.(k − 1) − (x − y ), x > y .обобщения:max(x1 , x2 , .
. . , xn ) = max(x1 , max(x2 , . . . , xn ));min(x1 , x2 , . . . , xn ) = min(x1 , min(x2 , . . . , xn ));x m = |x · .{z. . · x} — степень.mПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаЭлементарные функцииКак двузначные функции обобщаются на многозначныефункции?nn=0n=1n=2P20, 1xx̄x&yx ∨yx ⊕yx →yPk , k ≥ 30, 1, . . . , k − 1xx̄, ∼ xmin(x, y )max(x, y )x + y (mod k)x →yпоясненияконстантытождественная функцияотрицаниеконъюнкция или минимумдизъюнкция или максимумсложение по модулю kимпликацияВ связи с расширением исходного множества значенийпоявляются элементарные функции, не имеющие явногоэлементарного прообраза в двузначном случае: −x, Ji (x), ji (x),x −̇y .Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаФормулаПонятия формулы и функции, определяемой формулой,вводятся аналогично двузначному случаю.Пусть A ⊆ Pk .Формула над множеством A определяется по индукции.1.
Базис индукции. Если f n ∈ A — n-местная функция иu1 , . . . , un — набор из n произвольных имен переменных, товыражение f (u1 , . . . , un ) — формула.2. Индуктивный переход. Если F1 , . . . , Fn — уже построенныеформулы или имена переменных и f n ∈ A — n-местнаяфункция, то выражение f (F1 , . . . , Fn ) — формула.3. Других формул нет, т.е. каждая формула построена либо попо базису индукции, либо по индуктивному переходу.Конечнозначные функцииСпособы заданияНормальные формыПолиномыФормулыПример. Пусть A ⊆ P5 — множество элементарных функций.ТогдаF1 = x 2формула по базису индукции для функции x 2 ∈ A и имени переменной x;F2 = 3формула по базису индукции для функции 3 ∈ A;F3 = 3 · x 2формула по индуктивному переходу дляуже построенных формул F1 , F2 и функции x · y ∈ A;F4 =∼ (3 · x 2 )формула по индуктивному переходу дляуже построенной формулы F3 и функции∼ x ∈ A;и т.д.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыФункция, определяемая формулойКаждая формула над множеством A ⊆ Pk задает некоторуюk-значную функцию.Функция fF , задаваемая формулой F , определяется поиндукции.1.
Базис индукции. Если F = u, где u — имя переменной, тоfF = u, т.е. функция fF тождественно равна переменной u.2. Индуктивный переход. Если F = f (F1 , . . . , Fn ), гдеF1 , . . . , Fn — формулы или имена переменных и f n ∈ A, тоfF = f (fF1 , . . . , fFn ).ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыФункции, определяемые формуламиПример. Найдем функцию fF4 (x) ∈ P5 , которая задаетсяформулой F4 :x x 2 3 · x 2 ∼ (3 · x 2 )0 0041 1312 4233 4234 131Функция fF4 , определяемая формулой F4 , записана в самомправом столбце.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЭквивалентные формулыФормулы F1 и F2 называются эквивалентными, если ониопределяют равные функции, т.е.
функции fF1 и fF2 равны.Обозначение эквивалентных формул: F1 = F2Верны следующие свойства:1) коммутативность связок ·, +, min, max;2) ассоциативность связок ·, +, min, max;3) дистрибутивность умножения относительно сложения:(x + y ) · z = x · z + y · z.И многие другие.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыДоказательство эквивалентностейПримеры.1. Докажем эквивалентность: −(x̄) =∼ x.−(x̄) = −(x + 1) = (k − 1) − x =∼ x.2. Докажем эквивалентность: ∼ max(∼ x, ∼ y ) = min(x, y ).∼ max(∼ x, ∼ y ) == (k − 1) −(k − 1) − x, (k − 1) − x ≥ (k − 1) − y ;=(k − 1) − y , (k − 1) − x < (k − 1) − y ;x, x ≤ y ;== min(x, y ).y, x > y;ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнота1-я формаТеорема 2 (о 1-й форме).
Пусть k ≥ 2. Каждая k-значнаяфункция f (x1 , . . . , xn ) ∈ Pk может быть задана формулой вида:f (x1 , . . . , xn ) =max(σ1 ,...,σn )∈Eknmin (Jσ1 (x1 ), . . . , Jσn (xn ), f (σ1 , . . . , σn )) .Доказательство.Рассмотрим произвольный набор α = (a1 , .
. . , an ) ∈ Ekn . Тогдаf (a1 , . . . , an ) =max(σ1 ,...,σn )∈Eknmin (Jσ1 (a1 ), . . . , Jσn (an ), f (σ1 , . . . , σn )) == max(0, . . . , 0, f (a1 , . . . , an ), 0, . . . , 0) = f (a1 , . . . , an ).Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнота1-я формаПример.Пусть f (x) = x̄ ∈ P3 :x012f120Найдем ее 1-ю форму:f (x) = max(min(J0 (x), f (0)), min(J1 (x), f (1)), min(J2 (x), f (2))) == max(min(J0 (x), 1), min(J1 (x), 2), min(J2 (x), 0)) == max(min(J0 (x), 1), J1 (x)).Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнота2-я формаТеорема 3 (о 2-й форме) Пусть k ≥ 2. Каждая k-значнаяфункция f (x1 , .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
