Демонстрация работы сайта: папка «пример», файл сайт.htm.
СТРУКТУРНЫЕ ТЕГИ
<HTML> </HTML>
Тег, указывающий браузеру, что далее следует HTML-страница. Весь текст (HTML-код) должен находится между этими тегами. Открывающий тег <HTML> помещается в самом начале страницы, а закрывающий </HTML> - в самом конце.
<HEAD> </HEAD>
Тег заголовка HTML-страницы. Помещается в самом начале, после тега <HTML>. Между тегами заголовка ставится тег названия страницы <TITLE> </TITLE>.
<TITLE> </TITLE>
Между этими тегами помещается текст, являющийся названием страницы. Название HTML-страницы высвечивается в заголовке окна программы-браузера.
<BODY> </BODY>
Внутри этого тега пишется то, что будет доступно в области просмотра браузера (другими словами – тело страницы). Этот тег имеет несколько параметров.
<BODY
background=”URL”
bgcolor=цвет фона
text=цвет текста
link=цвет гиперссылки
alink=цвет активной гиперссылки
vlink=цвет просмотренной гиперссылки> </BODY>
Параметр background отвечает за обои HTML-странички. URL – путь к файлу, который вы выбрали в качестве обоев. Если этот файл поместить в ту же папку, что и HTML-страничку, то достаточно указать только имя файла.
Вместо слов «цвет фона» пишется текстовое или числовое значение цвета фона страницы, вместо «цвет текста» - текстовое или числовое значение цвета символов в тексте.
Параметры link, alink и vlink отвечают за цвет гиперссылок. Если они не указаны, тогда link и alink автоматически принимают значение «синий», а vlink – «лиловый».
Теги, управляющие внешним видом HTML-страницы
<Hn> </Hn>
Тег, определяющий размер и формат заголовков в тексте, n принимает значения от 1 до 5. Тест заголовка находится между открывающим и закрывающим тегами.
<Hn align=center½left½right> </Hn>
Выравнивание заголовка по центру½по левому краю страницы½по правому краю страницы. Если этот параметр не указан, то выравнивание автоматически производится по левому краю.
<P> (</P>)
Тег «параграф», отделяет абзацы друг от друга. Тест абзаца заключается между соответствующими тегами.
<P align=center½left½right > (</P>)
Выравнивание абзацев по центру½по левому краю страницы½по правому краю страницы. Если этот параметр не указан, то выравнивание автоматически производится по левому краю.
<B> </B>
Полужирное начертание символов, заключенных между открывающим и закрывающим тегами.
<I> </I>
Курсивное начертание символов.
<U> </U>
Подчеркивание символов.
<SUB> </SUB>
Подстрочный индекс.
<SUP> </SUP>
Надстрочный индекс.
<FONT
size=n
color=цвет символов
fase=название шрифта> </FONT>
Параметр size определяет размер шрифта в условных единицах от 1 (самый маленький) до 7 (самый большой).
Параметр color позволяет указать цвет шрифта.
Параметр fase определяет внешний вид шрифта в браузере (например, шрифт Arial или Times New Roman).
<BASEFONT> </BASEFONT>
Этот тег задает параметры шрифта для всей страницы. Изменить какой-то параметр можно только через тег <FONT> </FONT>
<HR>
Этот тег указывает на то, что браузер должен отобразить горизонтальную линию, идущую через весь экран.
<HR size=n width=m>
Параметром size определяется толщина линии в точках, n принимает значение от 2 до 7. Параметром widht задается длина линии, m принимает значение либо в точках, либо в процентах.
<HR color=цвет линии>
Вместо слов «цвет линии» пишется текстовое или числовое значение желаемого цвета.
<HR align=center½left½right >
Выравнивание горизонтальной линии по центру½по левому краю страницы½по правому краю страницы. Если этот параметр не указан, то выравнивание автоматически производится по левому краю.
Теги, отвечающие за размещение графических объектов
<IMG src= “Путь/Имя файла”>
Этот тег указывает на то, что браузер должен отобразить графический объект, имя которого указано в параметре src.
<IMG align=left½right src= “Путь/Имя файла”>
Выравнивание графического объекта по левому краю страницы½по правому краю страницы. Если этот параметр не указан, то выравнивание автоматически производится по левому краю.
Параметр width задает ширину (длину) графического объекта, параметр height определяет высоту. Значения m и h могут задаваться в точках или процентах. Если эти параметры не указаны, то размеры графического объекта будут исходными.
Параметр border заключает картинку в рамку, k – толщина рамки в точках.
Теги, отвечающие за создание списков
<OL type= 1 A a I i start=значение>
</OL>
Это тег отвечает за создание нумерованного списка. Элементы списка располагаются между открывающим и закрывающим тегами, каждый элемент объявляется тегом <LI>. Параметр type задает тип нумерации списка (по умолчанию – арабские цифры). Параметр start указывается тогда, когда необходимо начать нумерацию не с первого значения.
<LI>
Тег, объявляющий один элемент списка.
<UL type= square disk circle>
</UL>
Это тег отвечает за создание маркированного списка. Элементы списка располагаются между открывающим и закрывающим тегами, каждый элемент объявляется тегом <LI>. Параметр type задает тип маркера.
<DL> </DL>
Это тег отвечает за создание списка определений. Элементы списка располагаются между открывающим и закрывающим тегами.
<DT>
Тег, создающий элемент списка определений, являющийся термином.
<DD>
Тег, создающий элемент списка определений, являющийся определением.
Создание гиперссылок в языке HTML
<A NAME=“имя закладки”>Текст</A>
Создание в HTML-коде закладки для внутренней гиперссылки. На месте слова “Текст” ставится первое слово или фраза из текстового фрагмента, на который потом будет делаться ссылка.
<A HREF=“#имя закладки”>Текст </A>
Создание внутренней гиперссылки. То, что ссылка внутренняя указывается с помощью значка «#» в параметре HREF.
<A HREF=“Адрес страницы”>Текст </A>
Создание гиперссылки на Web-страницу, адрес которой записывается в параметре HREF.
Если в TARGET заносится имя фрейма, тогда страница, на которую указывает ссылка, будет отражена в этом фрейме.
Знак «_» перед следующими значениями TARGET показывает, что они не являются именами фреймов.
_blank – страница будет отображаться в новом чистом окне обозревателя.
_top – страница будет загружаться в самый верхний фрейм текущего окна.
_self – страница будет загружаться в то же окно, в котором находится ссылка, т. е. в текущее.
_parent –страница будет загружаться в текущее родительское окно фрейма. Если родительских окон не существует, то _parent становится тождественным _self.
Создание таблиц в языке HTML
<TABLE> </TABLE>
Этот тег отвечает за создание таблицы в языке HTML.
Если следующие параметры не указанны, тогда они принимают стандартные значения по умолчанию.
Выравнивание всей таблицы (по умолчанию left).
Определяет ширину всей таблицы, m принимает значение либо в точках, либо в процентах (от ширины окна).
Задает рамку таблице, k ширина рамки в точках (по умолчанию k=1). Если k=0, то создается таблица без рамки.
Определяет расстояние между ячейками в токах (стандартное равно 2).
Определяет расстояние между содержимым ячейки и ее границами в токах (стандартное равно 1).
<TR> </TR>
Тег, задающий одну строку таблицы.
Параметры тега
<TR
align=left½right | center
valign=top½bottom | middle> </TR>
Выравнивание содержимого ячеек в строке по вертикали (по левому½по правому краю / по центру).
Выравнивание содержимого ячеек в строке по горизонтали (по верхнему½по нижнему краю / по середине).
<TD> </TD>
Тег, задающий одну ячейку таблицы.
Параметры тега
<TD
align=left½right | center
valign=top½bottom | middle
width=m
bgcolor=” цвет ячейки“
rowspan=n
colspan=n
Выравнивание содержимого ячеек в строке по вертикали (по левому½по правому краю / по центру).
Выравнивание содержимого ячеек в строке по горизонтали (по верхнему½по нижнему краю / по середине).
Определяет ширину ячейки, m принимает значение либо в точках, либо в процентах (от ширины таблицы).
Определяет цвет ячейки.
Объединение в одном столбце n строк
Объединение в одной строке n столбцов
<TH> </TH>
Тег, задающий ячейку, в которой будет помещаться заголовок. Параметры этого тега аналогичны параметрам тега <TD> </TD>.
Создание фреймов в языке HTML
<FRAMESET> </FRAMESET>
Тег, определяющий набор фреймов и задающий общую структуру этого набора.
Вертикальная структура набора фреймов, n принимает значение в точках или в процентах. Символ “*” указывает, что на последний фрейм отводится вся оставшаяся часть окна.
Горизонтальная структура набора фреймов.
Задает ширину в точках всех фреймов, входящих в набор. Если n=0, все фреймы будут без рамок. По умолчанию border=5.
Это параметр может использоваться с тегами <FRAMESET> и <FRAME>. По умолчанию frameborder принимает значение yes и рамка имеет трехмерную форму. Если frameborder= “no”, тогда рамка фрейма будет невидимой.
Это параметр может использоваться с тегами <FRAMESET> и <FRAME>. Задает цвет рамки.
Это параметр может использоваться с тегами <FRAMESET> и <FRAME>. Задается цвет фона фрейма.
<FRAME>
Тег, описывающий каждый из фреймов, входящих в набор.
Параметр, дающий имя фрейму. Используется тогда, когда содержимое фрейма будет меняться, т. е. на этот фрейм будут делаться ссылки (если фрейму не присвоить имени на него нельзя будет ссылаться). Значение name используется в параметре target гиперссылки.
Вставка во фрейм конкретной HTML-страницы.
Параметры, задающий внутреннюю рамку фрейма. Отступ в n точек от верхней и нижней границы.
Отступ в m точек от правой и левой границы фрейма.
Параметр, задающий полосы прокрутки. Auto по умолчанию.
Параметр запрещающий менять границы фреймов (достаточно указать в одном фрейме, чтобы не менялись границы смежных с ним)
Используется для графической иллюстрации.
Определение: Множество называется универсальным для данной задачи, если все рассматриваемые в этой задаче множества являются его подмножествами.
Диаграммы Эйлера 1-го типа:
Диаграммы Венна 2-го типа:
для 1-го множества:
для 2-х множеств:
для 3-х множеств:
Пример
Операции над множествами
1.Пересечение
2.Объединение
3.Разность (относительное дополнение)
\
\
4.Дополнение (абсолютное)
\
5.Симметр. разность
\
Законы алгебры множеств
Алгебра множеств – совокупность тождеств, справедливых независимо от того, каково универсальное множество и какие именно подмножества обозначаются входящими в эти равенства буквами (отличных от и ).
a. Закон коммутативности
1)
2)
3)
b. Закон ассоциативности
1)
2)
3)
c. Закон дистрибутивности
1)
2)
1 способ (с пом. диагр.)
2 способ (поэлементное)
1)
2) или
d. Взаимодействие с самим множеством и его дополнением
1)
2)
3)
4)
e. Свойства нуля и единицы
1)
2)
3)
4)
Равенства алгебры множеств, полученное из другого заменой
6. Законы поглощения называется двойственным
1)
2)
7. Дополнение к и
1)
2)
8. Закон двойного дополнения
9. Признаки и
1) Если для то
2) Если для то
10. Законы де Моргана
1)
2)
11. Признак дополнения
Если то (или )
12. Свойства операций разности
\
1) \
2) \
3) \
4) \
Все рассмотренные законы двойственны.
Примеры:
1) Докажите тождества, используя законы алгебры множеств
а) (для сокращения записи опус. считаем что – более сильная операция )
б)
2) Упростите выражение с помощью заканов
а)
б) \\
в)
Обобщенные тождества алгебры множеств
1.Законы обобщенной дистрибутивности
1)
Доказательство (ММИ)
1 для
(по доказ. выше)
2 допустим формула верна для
Докажем, что она верна для
по доказ. В ш.1=
=по допущению
=
2)
2.Обобщенные законы де Моргана
1)
2)
Уравнения и системы уравнений алгебры множеств
Для решения уравнений и систем уравнений используются законы и важные утверждения:
Лемма 1
Доказательство (от противного)
1)Пусть , но , тогда
но
противоречие
2)Пусть но
-противор.
Лемма 2
Лемма 3
Лемма 4
Решение уравнения
где - некоторые подмножества универса,
-неизвестное множество
Множество называется решением, если формулы и задают одно и тоже множество.
По лемме 2 уравнение приводится к виду:
При помощи тождеств уравнение приводится к виду :
, где -некоторые множества
Это уравнение равносильно системе:
или - необходимые и достаточные условия существ. решения
Различные решения получаются при добавлении к «наименьшему» решению любых подмножеств разности \
Всего таких подмножеств - - число различных решений
Общее решение м. записать в параметр форме
, где - произв. множество из
Пример:
\
По л.2 \
НИД: выполняется и
Общ. режим: \
Число решений:
Проверка:
\
2)
(1)
(2)
НИД:
О.р. \
Число решений:
Проверка:
3) Система м. иметь един. решение
(1)
НИД:
Кол-во решений:1
Проверка:
4) Решением системы является любое подмножество
(1)
Число решений:
С/Р. Упростить систему условий:
1)
2)
Классификация множеств
Опред.: Говорят, что множество бесконечно, если из него можно взять некоторый элемент, после этого множество будет не пусто. И этот процесс можно повторять любое количество раз.
Простейшим примером является множество
1) Опред.: Множество называется счетным, если Счетным множеством называется всякое множество, элементом которого можно поставить во взаимнооднозначное соответствие множество натуральных чисел.
Отсюда, счетное множество – это бесконечное множество, элементы которого можно пронумеровать натуральными числами.
Примеры счетных множеств:
−множество
если
если
−множество всех четных положительных(отрицательных) чисел
В эту таблицу попадут все положительные рациональные числа, причем каждое из них встретится не один раз.
Будем выписывать дроби, проходя по диагонали, если встречаются равные дроби, их опускаем.
1 2 3
Присоединяя к множеству положительных рациональных чисел противоположные им отрицательные и «нуль», мы получим множество всех рациональных чисел.
Свойства счетных множеств:
Всякое подмножество счетного множества конечно или счетно.
Объединение любого конечного или счетного числа счетных множеств, есть счетное множество.
Любое бесконечное множество содержит счетное подмножество.
2) Опред.: Бесконечное множество, не явл. счетным, называется несчетным.
Опред.: Два множества называются эквивалентными, если м/у их элементами можно установить взаимно-однозначное соответствие.
Основное свойство бесконечных множеств:
Любое бесконечное множество эквивалентно своему истинному подмножеству.
Доказательство:
счетное подмножество бесконечного множества .
Разобьем на два счетных подмножества (с четными) и (с нечетными)
Соотношение
Теорема Кантора о существовании несчетных множеств:
Множество чисел, заключенных м\у нулем и единицей, несчетно.
Доказательство (от противного):
Пусть множество чисел счетно, представим каждое число в виде дроби:
Покажем, что существует такое число , которого нет среди перенумерованных чисел:
где
и т. д.
Полученное противоречие и доказывает теорему.
Опред.: Множество, эквивалентное множество действительных чисел, заключенных м\у нулем и единицей, называется множеством мощности континуум.
Теорема Кантора о существование множеств мощности более:
Пусть некоторое множество и буман, континуум тогда
Кардинальные операции над множествами. Прямое произведение множеств.
Кардинальными операциями называются такие операции, при применении которых в результирующем множестве появляются новые элементы.
Опред.: Прямым (декартовым) произведением множеств и называется множество всех упорядоченных пар, у которых первый элемент , второй .
Элементы пары и называется координатами.
Примеры:
1)
2)
Опред.: Множество называется прямым произведением n множеств.
упорядоченный набор длины называется вектором или кортежем.
Опред.: декартов квадрат
декартова степень.
Свойства прямого произведения
1.
2.или
или
Лемма о мощности прямого произведения двух множеств:
Доказательство:
Все элементы можно представить в виде матрицы:
Теорема о мощности прямого произведения множеств:
Доказательство (ММИ):
Следствие
Если то количество двоичных векторов длины .
Упражнения:
1)
а) Составьте множества
б) выписать 4 элемента
2) Изобразить
Покрытие и разбиение множества
Опред.: Покрытием множества называется совокупность подмножеств таких, что каждый элемент хотя бы одному из этих подмножеств.
Опред.: Разбиением множества на подмножеств называется совокупность попарно непересекающихся подмножеств таких, что каждый элемент одному и только одному из этих подмножеств.
- блоки разбиения
разбиение (и покрытие).
покрытие (но не разбиение).
Бинарные отношения
Опред.: Бинарным отношением (двуместным) из множества в множество называется подмножество прямого произведения .
, если , то называется отношением на .
Если , то говорят, что элементы и находятся в отношении .
Примеры: : «быть равным» на
: «быть» на множестве прямых
Представление бинарных отношений
1) В виде ориент. графа , где – множество вершин, – множество дуг.
Пример:
2) В виде матриц
3) С помощью верхнего и нижнего сечений
Верхним сечением элементы, стрелки которых направлены в .
Нижним сечением из .
Виды бинарных отношений
на множестве задано отношение
1) Бинарное отношение называется обратным, если
2) Бинарное отношение называется рефлексивным, если
3) Бинарное отношение называется антирефлексивным, если для всех
4) Бинарное отношение называется симметричным, если для из
5) Бинарное отношение называется антисимметричным, если из и
6) Бинарное отношение называется транзитивным, если из того что и
7) Бинарное отношение называется связным, если для всехили
Пример:1)
1. рефлексивно
2. антисимметрично
3. транзитивно
4. Связным
2) делит на
1. рефлексивно
2. антисимметрично
3. транзитивно
3)
1. антирефлексивно
2.
3. антитранзитивно
8) Дополнением к бинарному отношению называется
9) Композицией отношений называется отношение
которое определяется следующим образом:
10) Тождественное отношение:
11) Универсальное отношение:
Для бинарных отношений обычным образом определены теоретико-множественные операции или .
Свойства бинарных отношений
1)
2)
3) - рефлексивно
4) - симметрично
5) - транзитивно
6) - антисимметрично
7) - антирефлексивно
8) - связное
Специальные бинарные отношения
1)Опред.: Рефлексивное, симметричное и транзитивное отношение на множестве называется отношением эквивалентности
Пример: 1)
2)
Опред.: Пусть на множестве задано отношение эквивалентности.
Возьмём некоторый элемент и образуем множество состоящий из элемента
и всех эквивалентных ему элементов из .
Множество если оно не пусто, то выберем из него любой элемент и образуем множество и т. д.
До тех пор, пока в оставшейся части не останется ни одного элемента.
Полученная система подмножеств является разбиением и называется системой классов эквивалентности.
Свойства отношения эквивалентности
1. Класс эквивалентности порождается любым своим элементом
2. Всякое разбиение множества определяет отношение эквивалентности, если одному блоку разбиения
3. Всякое отношение эквивалентности определяет разбиение множества на классы эквивалентности
Примеры:
1) «иметь один и тот же остаток от деления на 3 (на )».
Три класса:
2)
3) книги библиотеки
переплет одного цвета
2)Опред.: Бинарное отношение называется отношением строго порядка, если оно антирефлексивно, антисимметрично и транзитивно.
Обозначение отношения порядка:
Если оно рефлексивно, антисимметрично и транзитивно, то оно является отношением не строгого порядка
Отображения
Отношения эффективно применяются для описания связей м/у пароли элементов, выбранных из двух множеств.
Опред.: Отображением (функцией) из в называется бинарное отношение такое, что:
1)
2)
Отображение называется инъективным, если
Отображение называется сюръективным, если
что
Отображение называется биективным, если оно инъективно и сюръективно
Примеры:
1) – неинъективно и несюръективно
2) неинъективно, сюръективно
3) инъективно, несюръективно
4)биективно
Упражнения
1) Упростите выражения
(с помощью диаграмм, с помощью законов)
2) Изобразить на диаграмме В-Э
3)
Изобразить:
4) Составьте множество всех подмножеств
а) б)
5) Запишите бинарное отношение
Запишите матрицу
6) и заданы матрицами
Построить матрицу композиции
7) Является ли отношением эквивалента или порядка (какого) на множестве
а) ,
б)
Раздел 1Булевы функции
Элементарные булевы функции от двух переменных
0 0
0 1
1 0
1 1
-конъюнкция (логическое умножение)
-дизъюнкция (логическое сложение)
-сумма по модулю 2 , т.е.
-импликация
-эквивалентность
-штрих Шеффера (антиконъюнкция)
-стрелка Пирса (антидизъюнкция)
Таблицы, в которых представлены значения булевых функций, называются таблицами истинности.
Опред.: Суперпозицией булевых функций называется функция , полученная с помощью подстановок функций друг в друга и переименованием переменных.
Выражение, описывающее эту суперпозицию, называется формулой алгебры логики.
Опред.: Формулы и называются эквивалентными, если соответствующие им функции равны.
Если функция соответствует формуле , то говорят, что формула реализует функцию .
Пример:
-суперпозиция
-формула
Несмотря на то, что каждой формуле соответствует какая-либо булева функция, понятия функции и формулы различны.
Формул бесконечно много, а функций – конечное число.
Свойства элементарных булевых функций
1. Коммутативность
2. Ассоциативность
3. Дистрибутивность
4. Взаимодействие с
5. Двойное отрицание
6. Законы де Моргана
7. Законы поглощения
8. Выражение эквивалентности через другие операции
9. Выражение через другие операции
10. Выражение импликации через другие операции
В справедливости можно убедиться, построив таблицы истинности этих формул.
Пример:
С помощью законов алгебры логики можно упрощать исходные формулы и получать новые.
Если в выражении нет скобок, то очередность логических операций следующая:
1) отрицание
2)
3)
4)
5)
Упражнения
1) Определить какие переменные являются фиктивными
3) Опираясь на законы проверить справедливость соотношений
а)
б)
Опред.: Функция, равносильная своей двойственной, называется самодвойственной.
показать, что является самодвойственной
В таблице истинности на всех парах противоположных наборов самодвойственная функция принимает противоположное значение.
Теорема двойственности
Если реализована формулой , то формула реализует функцию .
Доказательство:
Принцип двойственности
Пусть функция задана формулой через .
Для того, чтобы получить формулу, реализующую , достаточно заменить на , на , все константы на противоположные константы, функции и сохранить.
Двойственность функции
Опред.: Пусть булева функция, тогда такая, что называется двойственной к функции .
Примеры:
Таблица истинности для при упорядоченном наборе значений переменной получается из таблицы для построением и переворачиванием столбца значений от .
Доказательство:
Рассмотрим значение формулы в правой части на наборе значений
Все конъюнкции, в которых равны , их можно опустить, поэтому в дизъюнкции останется одно слагаемое
Так как набор значений переменной выбран произвольно, то формула верна всегда.
Следствие 1:
Следствие 2:
СДНФ
Теорема: Всякая булева функция имеет единственное СДНФ.
Доказательство:
Пример:
1)
2)
Разложение булевых функций по переменным
Введем обозначение:
0 0
0 1
1 0
1 1
Теорема: Каждую функцию алгебры логики можно представить в виде:
, где дизъюнкция берется по всевозможным наборам .
5)Если в конъюнкцию не входит переменная , то нужно рассмотреть равносильное выражение и вновь перейти к шагу 2.
6) Если появились одинаковые конъюнкции вновь перейти к шагу 3.
Пример:
1)
2)
Опред. Выражение вида
Называется СКНФ
1)
Каждое из выражений называется элементарной конъюнкцией.
СДНФ называется совершенной, так как каждое слагаемое содержит все переменные;
дизъюнктивной, так как главная операция-дизъюнкция;
нормальной, так как совершенный вид такой формы является однозначным способом записи формулы, реализующей заданную функцию.
1. Табличный способ построения СДНФ
2. Аналитический способ построения СДНФ
1) Преобразуем формулу так, что бы в ней были только , причем могут стоять только над переменными
2) Используя законы дистрибутивности, преобразуем формулу так, чтобы выполнялись раньше, чем .
3) Если в ДНФ имеется несколько одинаковых конъюнкций, то оставляем лишь одну.
4) Делаем все конъюнкции правильными
Упражнения: построить СДНФ и СКНФ
1)
2)
Полином Жегалкина
Теорема:
Всякую булеву функцию можно представить в виде:
, где сумма по берется по всем наборам, где
Подставим вместо выражение , раскрыв скобки по закону дистрибутивности и приведя подобные члены по правилу , придем к представлению в виде:
,
где коэффициенты или .
Это представление носит название полинома Жегалкина.
2.
3. Чтобы построить СКНФ для некоторой функции, надо построить отрицание в СДНФ, то есть взять дизъюнкцию элем. конъюнкций, дающих значение 0 и взять отрицание от .
Пример:
2) Метод неопределенных коэффициентов
Опред.: Если ПЖ не содержит конъюнкций, то есть имеет вид , то соответствующая ему функция называется линейной.
Упражнения
Построить ПЖ
1)
2)
3)
Теорема: Всякая булева функция может быть представлена в виде полинома Жегалкина единственным образом.
Если у функции есть фиктивные переменные, то они н6е должны входить в ПЖ.
Способы нахождения ПЖ:
1) С помощью законов алгебры логики
а) из исходной формулы
б) из СДНФ
Следствие:
Полными являются системы:
Доказательство:
а)
б)
Доказать самостоятельно: полные системы
Замыкание
Опред.: Пусть некоторый класс (подмножество) булевых функций .
Замыканием называется множество всех булевых функций, представимых в виде суперпозиции функций из .
1)
2)
множество всех линейных функций
Полнота и замкнутость
Опред.: Система функций называется функционально полной, если любая булева функция может быть представлена в виде суперпозиции функций этой системы.
Пример: 1) полная
2) полная
Доказательство:
Если , то
Если , то её можно представить в виде СДНФ
3) неполная
Теорема о полноте второй системы булевых функций
Пусть даны 2 системы и , причем 1 – полная и каждая функция системы (1) выражается в виде суперпозиции функций системы (2).
В этом случае система (2) является полной (без доказательства).
2) Класс класс функций, сохраняющих константу «1», то есть
Примеры:
Теорема замкнутый класс (доказать самостоятельно)
3) Класс класс самодвойственных функций, то есть
Примеры:
Так как самодвойственная функция на противоположных наборах принимает противоположные значения, то самодвойственные функции определяются своими значениями полностью на первой половине строк
Теорема: замкнутый класс
где
Свойства замыкания
1)
2)
3)
4)
Опред.: Класс называется функционально замкнутым, если
1) замкнут
2) не замкнут
3) замкнут
Важнейшие замкнутые классы
1) Класс класс функций, сохраняющих константу 0, то есть
Пример:
Теорема: замкнутый класс
Функцию , где
2)
3)
4) Класс класс монотонных функций
Введем обозначение:
наборы значений переменной
значение функции на этих наборах
Опред.: Наборы и находятся в отношении предшествования ,
если
несравнимы
Опред.: Булева функция называется монотонной, если и таких, что выполняется неравенство
Лемма о несамодвойственной функции
Если , то из неё путем подстановки и вместо переменных можно получить константу.
Доказательство:
Так как , то такой набор , что
Функцию (делаем замену )
Так как
Пример: Можно ли получить константу из функции
1)
Замена:
или
Лемма о немонотонной функции
Если функция не является монотонной, то из неё с помощью подстановки 0,1 и вместо переменных можно получить .
Доказательство:
Пусть , тогда и
наборы
функцию
Пример: Определить, можно ли получить функцию из функции:
1) , так как
Делаем замену:
, если
, если
так как
Проверять монотонность можно с помощью диаграммы:
1) Хассе
Пример:
(1,1)
(0,1) (1,0)
(0,0)
Если при движении по каждому ребру значение функции не уменьшается, то функция является монотонной.
Следовательно, не монотонна.
2) Разделим вектор не две равные части, если , то функция не является монотонной.
Если , то каждый из векторов вновь разделим на 2 равные части и так далее.
Если выполняется для всех пар, то .
Пример:
не сравнимы
функция не является монотонной.
Теорема: Класс замкнутый класс
Доказательство:
Пусть , функция не является линейной относительно и , тогда
где
Выберем такой набор , что
Подставим
Обозначим
Можно заметить, что
То есть
Пример: Выяснить является ли функция линейной, если нет, то построить
1)
с/р 2)
5) Класс класс линейных функций
Примеры:
Теорема: Класс замкнутый класса
Лемма о нелинейной функции
Если функция нелинейная, то из неё с помощью подстановки 0,1, а также и быть может навешивания отрицания над всей функцией можно получить конъюнкцию .
Система булевых функций является полной когда она целиком не содержится ни в одном из замкнутых классов: .
2 Достаточность
Пусть не содержится ни в одном из классов, тогда функции такие, что
Достаточно показать, что эта система является полной.
Для доказательства получим отрицание, константы, :
Возьмем , то есть
Функцию
Случай (а): получили , берем и по лемме 10 несом. функции получаем вторую константу. Таким образом, имеем систему по лемме 30 нелинейные функции, получаем .
Случай (б): , так как , то , то есть получены обе константы.
Берем функцию и получаем по лемме 0 немон. функции
получаем аналогично.
Таким образом мы выразили через функции , так как полная, то полная.
2)
с/р 3)
Все рассмотренные 5 классов не полные и попарно различны, то есть булевы функции, не принадлежащие ни одному из классов, и есть функции одному из любых 2-ух классов.
Теорема о функциональной полноте – критерий полноты, системы булевых функций. (Теорема Поста)
Примеры базисов:
Следствие 1 из теоремы Поста:
Каждый базис в алгебре логики состоит не более чем из 4-х функций.
Доказательство:
1) Пусть , по теореме Поста полная.
Покажем, что можно удалить одну из функций и система останется полной.
Функцию .
1) , удаляем
полная
2) , удаляем
полная
2) Покажем, что базис алгебры логики из 4-х функций
Система полная, любая подсистема не является полной(нельзя исключить ни одну функцию).
Пример
-
+
-
-
-
-
+
-
-
+
-
-
+
-
+
содержится целиком в классе система не является полной
Если добавить то система будет полной, если исключить из то система также будет полной
Опред.: Полная система функций, которая при удаление из неё любой функции становится неполной, называется базисом.
Систему
Базис:
+
-
-
+
+
-
+
-
+
+
+
+
-
+
-
+
-
-
-
+
3)Получение конъюнкции (по лемме о нелинейной функции)
Пример 2:
Выяснить, полна ли система функций. Если полна, то провести поэтапное доказательство теоремы Поста.
Одной из целей булевой алгебры является описание поведения и структуры логических схем.
Логическая схема имеет вид «черного ящика», в котором вход – набор булевых переменных, а выход булева функция.
Исследователя интересуют лишь входные и выходные сигналы, а не процессы протекания.
Примерами логических схем служат микросхемы.
В электротехнике принята маркировка по той функции, которую схема реализует:
и –не , 2и –не и так далее.
Достаточно выразить в виде функции от переменных
Опред.: Класс называется предполным, если неполный, но при добавлении любой функции он становится полным.
Следствие 2: Существует только 5 предполных классов: .
Пример 1: Доказать полноту системы функций .
Выразить константы, и через функции этой системы.
-
+
-
-
-
+
-
-
-
+
Система является полной.
1) Получение констант (по лемме о несамодвойственной функции)
2) Получение отрицания (по лемме о не монотонной функции)
Сравнивая операцию двоичного сложения и суммы по модулю 2 можно увидеть аналогично.
Операция двоичного сложения в пределах последнего двоичного разряда имеет ту же последовательность символов, что и сумма по модулю 2.
Поэтому операция сложения по модулю 2 имеет особое значение для организации работы компьютера: в схемах контроля и исправления ошибок.
называется универсальным для данной задачи, если все рассматриваемые в этой задаче множества являются его подмножествами.
\
\
).
или 
называется двойственным
то 
то 
то 
(или 
)
(для сокращения записи опус. 
считаем что 
\
\
(по доказ. выше)
по доказ. В ш.1=
по допущению
, но 
, тогда
но 
но 
-противор.
- некоторые подмножества универса,
-неизвестное множество
называется решением, если формулы 
и 
задают одно и тоже множество.
, где 
-некоторые множества
или 
- необходимые и достаточные условия существ. решения
любых подмножеств разности 
- число различных решений
, где 
- произв. множество из 
выполняется 
\
\
Всякое подмножество счетного множества конечно или счетно.
Объединение любого конечного или счетного числа счетных множеств, есть счетное множество.
Любое бесконечное множество содержит счетное подмножество.
счетное подмножество бесконечного множества 
.
(с четными) и 
(с нечетными)
, которого нет среди перенумерованных чисел:
где
и т. д.
некоторое множество и 
буман, континуум тогда 
, второй 
.
и 
называется координатами.
называется прямым произведением n множеств.
упорядоченный набор длины 
называется вектором или кортежем.
декартов квадрат
декартова 
степень.
или 
или 
то 
количество двоичных векторов длины 
выписать 4 элемента
таких, что каждый элемент 
хотя бы одному из этих подмножеств.
таких, что каждый элемент 
- блоки разбиения
разбиение (и покрытие).
покрытие (но не разбиение).
(двуместным) из множества 
в множество 
называется подмножество прямого произведения 
.
, если 
, то 
называется отношением на 
, то говорят, что элементы 
находятся в отношении 
: «быть равным» на 
: «быть» на множестве прямых
, где 
– множество вершин, 
элементы, стрелки которых направлены в 
из 
на множестве 
называется обратным, если 
из 
и
или 
рефлексивно
антисимметрично
транзитивно
рефлексивно
антисимметрично
транзитивно
антирефлексивно
антитранзитивно
называется отношение
которое определяется следующим образом:
состоящий из элемента 
если оно не пусто, то выберем из него любой элемент 
и т. д.
одному блоку разбиения
«иметь один и тот же остаток от деления на 3 (на 
такое, что:
– неинъективно и несюръективно
неинъективно, сюръективно
инъективно, несюръективно
биективно
б) 
, 
, т.е. 
называется функция 
, полученная с помощью подстановок функций друг в друга и переименованием переменных.
и 
-суперпозиция
-формула
через другие операции
; составить табл. истин.
показать, что является самодвойственной
реализована формулой 
, то формула 
реализует функцию 
.
.
, достаточно заменить 
сохранить.
булева функция, тогда 
такая, что 
называется двойственной к функции 
и переворачиванием столбца значений от 
равны 
, их можно опустить, поэтому в дизъюнкции останется одно слагаемое
СДНФ
можно представить в виде:
, где дизъюнкция берется по всевозможным наборам 
.
и вновь перейти к шагу 2.
называется элементарной конъюнкцией.
могут стоять только над переменными
, где сумма по 
берется по всем наборам, где 
выражение 
, раскрыв скобки по закону дистрибутивности и приведя подобные члены по правилу 
, придем к представлению в виде:
,
или 
.
, то соответствующая ему функция называется линейной.
полные системы
некоторый класс (подмножество) булевых функций 
.
называется множество всех булевых функций, представимых в виде суперпозиции функций из 
называется функционально полной, если любая булева функция может быть представлена в виде суперпозиции функций этой системы.
полная
полная
, то 
, то её можно представить в виде СДНФ
неполная
и 
, причем 1 – полная и каждая функция системы (1) выражается в виде суперпозиции функций системы (2).
класс функций, сохраняющих константу «1», то есть 
класс самодвойственных функций, то есть 
где 
замкнут
не замкнут
замкнут
класс функций, сохраняющих константу 0, то есть 
, где
наборы значений переменной
значение функции на этих наборах
и 
находятся в отношении предшествования 
,
несравнимы
и 
выполняется неравенство 
, то из неё путем подстановки 
такой набор 
, что 
(делаем замену 
)
Замена:
или
, тогда 
и 
, так как
, если 
, если 
(1,1)
не монотонна.
не две равные части, если 
, то функция не является монотонной.
, то каждый из векторов вновь разделим на 2 равные части и так далее.
.
, функция не является линейной относительно 
и 
, тогда
где 
, что 
класс линейных функций
и быть может навешивания отрицания над всей функцией можно получить конъюнкцию 
.
когда она целиком не содержится ни в одном из замкнутых классов: 
.
не содержится ни в одном из классов, тогда 
такие, что 
, то есть 
и по лемме 10 несом. функции получаем вторую константу. Таким образом, имеем систему 
по лемме 30 нелинейные функции, получаем 
, так как 
, то 
, то есть получены обе константы.
и получаем по лемме 0 немон. функции 
через функции 
, так как 
полная, то 
полная.
с/р 3) 
одному из любых 2-ух классов.
, по теореме Поста 
полная.
.
, удаляем 
полная
, удаляем 
полная
Система полная, любая подсистема не является полной(нельзя исключить ни одну функцию).
система не является полной
будет полной, если исключить из 
то система 
также будет полной
неполный, но при добавлении любой функции 
он становится полным.
.
