Слайд 2
В России эта ступень подготовки введена в 1993
году. С 31 декабря 2010 года «бакалавр» и «магистр»
- основные квалификациями для поступающих в российские вузы. Таким образом, степень «бакалавр» – это законченное базовое высшее образование.
Нормативный срок обучения составляет 4 года для очной формы обучения. Квалификация (степень) бакалавра присваивается после сдачи выпускных экзаменов и защиты выпускной работы.
Диплом бакалавра даёт право на работу по специальности и (или) поступление в магистратуру. В отличие от подготовки специалистов программы бакалавриата подразумевают широкопрофильное обучение. Другими словами, бакалавры получают фундаментальное образование без узкой специализации.
АКАДЕМИЧЕСКАЯ СТЕПЕНЬ «БАКАЛАВР»
Бакалавр (от латинского «baccalarius» – «молодой человек») – первая академическая степень в многоуровневой структуре высшего профессионального образования.
Слайд 3
АКАДЕМИЧЕСКАЯ СТЕПЕНЬ «БАКАЛАВР»
Слайд 4
Образовательная программа — согласно Федеральному закону № 273 от 29
декабря 2012 года «Об образовании в Российской Федерации» комплекс
основных характеристик образования (объем, содержание, планируемые результаты), организационно-педагогических условий и в случаях, предусмотренных настоящим Федеральным законом, форм аттестации, который представлен в виде учебного плана, календарного учебного графика, рабочих программ учебных предметов, курсов, дисциплин (модулей), иных компонентов, а также оценочных и методических материалов.
ПОНЯТИЕ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ
Слайд 5
ЛИТЕРАТУРА
В.Ф. Пономарев. Математическая логика. Часть 1. Логика высказываний.
Логика предикатов. Учебное пособие – Калининград: КГТУ, 2001.
В.Ф. Пономарев.
Дискретная математика для инженеров: Учебное пособие.- М.: Горячая линия –Телеком, 2009.
Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин.-2-е изд., стер.- М.: Издательский центр «Академия», 2008.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин.-3-е изд., стер.- М.: Издательский центр «Академия», 2007.
Слайд 6
РОЛЬ И МЕСТО ЛОГИКИ В МЫШЛЕНИИ, В НАУКЕ,
В МАТЕМАТИКЕ И В ОБУЧЕНИИ
Логическое (дедуктивное) мышление – от
истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт и интуиции . Логическое мышление протекает на уровне сознания.
Интуиция (от лат. intutio – «пристальное всматривание») – способность постижения истины прямым усмотрением без логически строгого доказательства. Интуитивное мышление протекает на подсознательном уровне.
Слайд 7
ЛОГИКА ТРАДИЦИОННАЯ
Логика (от греч. λογοζ (логос, смысл,
слово, понятие) – наука о способах доказательств или опровержений.
Традиционная
или формальная логика – наука, берущая свое начало от учения Аристотеля и изучающая формы и законы мышления, а также методы рассуждений людей.
Слайд 8
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Готфрид Лейбниц заложил основы математической логики. Он
пытался построить первые логические исчисления (свести логику к математике).
Он предложил использовать символы вместо слов. Поставил задачи по созданию символьной логики.
Немецкий ученый
Готфрид Лейбниц
(1646 – 1716)
Англичанин, математик-самоучка
Джорж Буль
(1815 – 1864)
Джорж Буль создал Булеву алгебру или алгебру высказываний. В его работах логика обрела свой алфавит,, свою орфографию и грамматику.
Математическая (символьная, теоретическая) логика – применила математические методы для изучения общих структур (форм) правильного мышления и оформилась как раздел математики.
Значительный вклад в развитие математической логики внесли советские математики: Н.А. Васильев, И.И. Жегалкин, А.Н. Колмогоров, П.С. Новиков, А.А. Марков, А.И. Мальцев, С.А. Яновская.
Слайд 9
Математическая логика включает: теорию моделей, теорию доказательств и
теория алгоритмов.
Теория моделей — изучает фундаментальные взаимосвязи между синтаксисом и семантикой. Название «теория
моделей» было впервые предложено Альфредом Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.
Теория доказательств – раздел математической логики, в котором само понятие математического доказательства становится предметом изучения. Математики обосновывают свои теоремы путём предъявления их доказательства (алгебра высказываний, булевы функции, логика (исчисление) высказываний, логика предикатов).
Теория алгоритмов — раздел математической логики, изучающий общие свойства алгоритмов, вычисляемых с их помощью функций, а также разнообразные модели вычислений.
ОБЛАСТИ ИССЛЕДОВАНИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
Слайд 10
АЛГЕБРА ВЫСКАЗЫВАНИЙ
Алгебра высказываний (логики) – раздел теории доказательств,
изучающий высказывания и логические операции над ними.
Высказывание – важнейший
объект изучения математической логики, это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Иными словами утверждение об истинности или ложности высказывания должно иметь смысл. Высказывание не должно одновременно быть истинным и ложным. Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности, или истинностным значением.
Примеры высказываний: подстанция работает в нормальном режиме, авария на линии электропередач, температура в помещении выше нормы, короткое замыкание в сети.
Примеры предложений не являющихся высказываниями: фамилия диспетчера? (вопрос); прочтите инструкцию дежурного диспетчер ( приказ или восклицание); все что вы говорите - неправда (внутренне противоречивое утверждение).
Слайд 11
ВЫСКАЗЫВАНИЯ
Например, предложение:
«З - простое число» является истинным,
«3.14… - рациональное число" является ложным;
"Колумб открыл Америку"
является истинным,
"Киев - столица Узбекистана" является ложным;
“число 6 делится на 2 и 3” является истинным,
“сумма чисел 2 и 3 равна 6” является ложным.
Такие высказывания называют простыми или элементарными.
При формальном исследовании сложных текстов понятие “простые высказывания” замещают понятием “пропозициональные переменные”, которые обозначают прописными буквами латинского алфавита “A”, “B”, “C”,…
Истинность или ложность высказывания будем отмечать символами “и” – истина или “л” – ложь.
Слайд 12
Пример:
если A1 := “3 - простое число”, то
A1 = и;
если A2 := “3 - вещественное число”,
то A2 = и;
если A3 := “3 - целое число”, то A3 = и;
если B1 := “3, 14…- рациональное число”, то B1 = л;
если B2 := “3, 14…- не рациональное число”, то B2 = и;
если C := “Колумб открыл Америку”, то C = и;
если D := “Киев - столица Узбекистана”, то D = л;
если E := “Число 6 делится на 1, 2 и 3”, то E = и;
если G := “Число 6 есть сумма чисел 1, 2, 3”, то G = и.
Примечание: символ “ := ” означает, что пропозициональной переменной, стоящей слева, присвоить значение высказывания, стоящего справа.
ВЫСКАЗЫВАНИЯ
Слайд 13
Высказывания, которые формируют из простых предложений с помощью
грамматических связок “не”, “и”, “или”, “если … , то
…”, “… тогда и только тогда, когда …” и т.п., называют сложными.
Для обозначения грамматических связок в формальном языке вводят символы, которые называют логическими связками.
Например, ∨ : = ”или”, & : = “и”, ⎤ : = ”не”, → : = “если … , то …”, ↔ : = “… тогда и только тогда, когда.
Для построения более сложных высказываний используют вспомогательные символы “(“, “)” - скобки.
СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ СВЯЗКИ
Слайд 14
Пример:
если высказывание: “3 – вещественное и целое
число”, то формула (A1&A2) = и;
если высказывание: “число 6
делится на 1, 2, 3 и представляет сумму делителей 1, 2, 3”, то формула (E&G) = и;
для высказывания: “если 3 - целое число, то оно вещественное”, справедлива формула (A3→ A2) = и;
для высказывания “3 - простое число тогда и только тогда, когда оно целое”, справедлива формула (А1↔А2) = и.
СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ СВЯЗКИ
A1 := “3 - простое число”;
A2 := “3 - вещественное число”;
A3 := “3 - целое число”;
B1 := “3, 14…- рациональное число”;
B2 := “3, 14…- не рациональное число”;
C := “Колумб открыл Америку”;
D := “Киев - столица Узбекистана”;
E := “Число 6 делится на 1, 2 и 3”;
G := “Число 6 есть сумма чисел 1, 2, 3”.
Слайд 15
Правила построения сложных высказываний в виде последовательности пропозициональных
переменных, логических связок и вспомогательных символов определяют возможность формального
описания любого текста естественного языка.
Логические связки позволяют сохранять или изменять логическое значение сложного высказывания, относительно простых высказываний. Поэтому логические связки обозначают логические операции над высказываниями. Правила исполнения логических операций над высказываниями формирует алгебру высказываний.
При формальном описании сложного высказывания всегда нужно исходить из его содержания. До тех пор пока не определена логическая структура сложного высказывания, его нельзя формально описывать.
Высказывания, из которых делают вывод новых высказываний, называют посылками, а получаемое высказывание – заключением.
СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ СВЯЗКИ
Слайд 16
Совокупность пропозициональных переменных T = {A, B, C,…}
и логических операций F = { ⎤, &,
∨, →, ↔ } формируют алгебру высказываний:
Aв = < T, F >.
Символы логических операций заданы логическими связками:
⎤ - отрицание, & - конъюнкция, ∨ - дизъюнкция, → - импликация, ↔ - эквиваленция.
Сложное высказывание составляемое из элементарных высказываний посредством логических связок, называют формулой алгебры логики.
Любая пропозициональная переменная есть элементарная формула, т. е. Ai = Fi. Если F1 и F2 – формулы, то ⎤F1, ⎤F2, (F1&F2), (F1∨F2), (F1→F2) и (F1 ↔ F2) также формулы. Никаких других формул в исчислении высказываний нет.
Значение формулы полностью определяется значениями входящих в нее пропозициональных переменных.
АЛГЕБРА ВЫСКАЗЫВАНИЙ
Слайд 17
Логические операции бывают унарными (одноместными) и бинарными (двухместными).
Это определяется наличием одного или двух операндов. Результаты логических
операций также принадлежат множеству {и; л} и их удобно описывать таблицами истинности.
Отрицание (⎤ F) есть одноместная операция, посредством которой ее значение есть отрицание значения операнда.
В программировании для этого используют оператор NOT: (NOT F) истинно тогда и только тогда, когда F ложно.
Таблица истинности
Пример: верно ли, что высказывание “А := “4 - простое число” истинно?
Нет, “неверно, что 4 – простое число”. Тогда ⎤ А = и .
ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Если F - высказывание, то ⎤F также высказывание.
Если ⎤F есть высказывание, то ⎤(⎤F) также есть высказывание.
Слайд 18
Конъюнкция (F1 & F2) есть двухместная операция, посредством
которой из двух формул F1 и F2 получают новую
формулу F = (F1&F2), описывающую сложное высказывание.
В программировании для этого используют оператор AND: (F1_AND_F2) истинно тогда и только тогда, когда истинны значения двух операндов F1 и F2.
Если даны формулы F1, F2 ,…, Fn, то формула F = (F1&F2&…&Fn) = и тогда и только тогда, когда истинны все формулы F1, F2 ,…, Fn.
На естественном языке эта операция выражается соединительными словами: “...и…“, “...также…“, “как...,так..“, “...несмотря на ...“ и др.
Пример: даны высказывания A := "компьютер содержит основной микропроцессор", B := "компьютер содержит оперативную память", C := ”компьютер содержит контроллеры"; D := "компьютер содержит порты ввода - вывода". Тогда формула F = (A&B&C&D) отражает высказывание "компьютер содержит основной микропроцессор, оперативную память, контроллеры и порты ввода-вывода".
ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Слайд 19
Дизъюнкция (F1∨F2) есть двухместная операция, посредством которой из
двух формул F1 и F2 получают новую формулу F
= (F1∨F2), описывающую сложное высказывание.
В программировании для этого используют оператор OR: (F1_OR_F2) ложно тогда и только тогда, когда ложны значения двух операндов F1 или F2.
Из определения операций дизьюнкции и отрицания очевидно, что (F∨⎤F) = и. В естественном языке эта операция выражается разъединительными словами “..или..“, “..либо.. “ и т.п.
Если даны формулы F1, F2,…, Fn, то значение формулы F = (F1∨F2∨…∨Fn) = и определяется значением “и” хотя бы одной формулы F1, F2,…,или Fn.
ЛОГИЧЕСКИЕ ОПЕРАЦИИ ДИЗЪЮНКЦИЯ
Слайд 20
Следует обратить внимание, что в повседневной речи союз
“или” употребляется в двух смыслах: “исключающее или”, когда истинность
составного высказывания определяется истинностью только одного из двух или нескольких высказываний, и “не исключающее или”, когда истинность сложного высказывания определяется истинностью хотя бы одного из них.
Пример: даны высказывания A := "в компьютере применяют матричный принтер", B := "в компьютере применяют струйный принтер", C := "в компьютере применяют лазерный принтер"; D := "в компьютере применяют литерный принтер". Тогда формула F = (A∨B∨C∨D) отражает высказывание "в компьютере применяют матричный, струйный, лазерный или литерный принтеры".
ЛОГИЧЕСКИЕ ОПЕРАЦИИ
ДИЗЪЮНКЦИЯ
Слайд 21
Импликация (F1→F2) есть двуместная операция, посредством которой из
формул F1 и F2 получают новую формулу F =
(F1→F2), отражающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда истинно значение F1 и ложно F2.
В программировании используют оператор IMPLIES: (F1 IMPLIES F2) ложно тогда и только тогда, когда истинно F1 и ложно F2.
На естественном языке эта операция выражается словами "если ..., то ... ", "тогда ..., когда ... ", "постольку ..., поскольку ... ", "при наличии ..., следует ... ", и т. п. F1 называют посылкой, а F2 –заключением
Пример: даны высказывания A:="по проводнику протекает электрический ток" и B - "вокруг проводника есть магнитное поле". Тогда формула F = (A→B) отражает высказывание "если по проводнику протекает электрический ток, то вокруг проводника возникает магнитное поле".
ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Слайд 22
Эквиваленция (F1↔F2) есть двухместная операция, посредством которой из
двух формул F1 и F2 получают новую формулу F
= (F1↔F2), описывающую сложное высказывание.
В программировании для этого используют оператор IFF: (F1 IFF F2) истинно тогда и только тогда, когда оба операнда F1 и F2 имеют одинаковые значения.
На естественном языке эквиваленция выражается словами «для того, чтобы ..., необходимо и достаточно ...», « ... лишь при условии...» и т. п.
ЛОГИЧЕСКИЕ ОПЕРАЦИИ ЭКВИВАЛЕНЦИЯ
Слайд 23
Пример: даны высказывания A := “выполнить загрузку в
компьютер операционной системы” и B := “установить в компьютер
дискету с записанной операционной системой“. Тогда формула F = (A↔B) отображает высказывание “для того, чтобы выполнить загрузку операционной системы в компьютер, необходимо и достаточно установить в компьютер дискету с записанной операционной системой".
Пример: даны высказывания A := ”урожай будет стабильным ежегодно” и B := "выполнены все ирригационные работы". Тогда формула F = (A↔B) отображает высказывание "урожай будет ежегодно стабильным тогда и только тогда, когда будут выполнены все ирригационные работы".
ЛОГИЧЕСКИЕ ОПЕРАЦИИ ЭКВИВАЛЕНЦИЯ
Слайд 24
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Для определения истинности суждения необходимо
анализировать значение истинности каждого элементарного высказывания и формировать последовательно
значение истинности каждой подформулы, входящей в формулу сложного суждения. Логические значения сложной формулы также удобно описывать таблицами истинности.
Пример: суждение "если инвестиции на текущий год не изменятся, то возрастает расходная часть бюджета или возникает безработица, а если возрастет расходная часть бюджета, то налоги не будут снижены и, наконец, если налоги не будут снижены и инвестиции не изменятся, то безработица не возникнет".
В этом суждении есть четыре повествовательных предложения: A := ”инвестиции на текущий год не изменяются”, B := ”возрастает расходная часть бюджета”, C := ”возникает безработица”, D := ”налоги не снижаются”
Тогда формула сложного суждения имеет вид:
F = (A→(B∨C))&(B→D)&((D&A)→ ⎤C).
Слайд 25
F = (A→(B∨C))&(B→D)&((D&A) → ⎤C).
В 12-ом столбце
таблицы выделены те строки, в которых формула имеет значение
истины при различных значениях пропозициональных переменных A, B, C и D.
Анализ таблицы показывает: для того, чтобы не возникла безработица, нужно не снижать налоги (D = и) при любых инвестициях (А = и или А = л) и расходной части бюджета (В = и или В = л).
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Для удобства записи любой подформулы и формулы каждый столбец пронумерован, и логические операции выполняются с индексами столбцов.
Слайд 26
Пример:
суждение: “Если цены высокие (A), то и
заработная плата должна быть также высокой (B). Цены высокие
или применяется регулирование цен (C). Если применяется регулирование цен, то нет инфляции (⎤D). Инфляция есть. Следовательно, заработная плата должна быть высокой”.
Формулы первых четырех высказываний формируют посылки, а формула пятого высказывания – заключение, т. е.
A→B; A∨C; C→⎤D; D
B.
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Слайд 27
Выделенная четырнадцатая строка таблицы показывает, при каких значениях
A, B, C и D истинны посылки и заключение.
Анализ показывает, что заработная плата при высоких ценах и наличии инфляции должна быть высокой и не должно быть регулирования цен.
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
A→B; A∨C; C→⎤D; D
B
Слайд 28
Пример:
суждение “если курс ценных бумаг возрастет (A)
или процентная ставка снизится (B), то курс акций упадет
(C) или налоги не повысятся (D); курс акций падает тогда и только тогда, когда растет курс ценных бумаг и растут налоги; если процентная ставка снизится, то либо курс акций не понизится, либо курс ценных бумаг не возрастет. Следовательно, если налоги повысить, то не вырастет курс ценных бумаг и вырастет курс акций”.
В этом суждении четыре сложных высказывания, три из которых являются посылками, а одно – заключением:
(A∨B)→(C∨D); C↔(A&⎤D); B→(⎤C∨⎤A)
(⎤D→(⎤A&⎤С )).
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Слайд 29
Выделенные строки таблицы показывают, при каких значениях A,
B, C и D истинны посылки и заключение. Так
как для всех шести вариантов значение С = л, то оказывается возможным рассмотреть истинность заключения для четырех вариантов:
(А = и)&(D = и),
(А = и)&(В = л),
(В = л)&(D = и),
(В = и)&(D = л).
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
(A∨B)→(C∨D); C↔(A&⎤D); B→(⎤C∨⎤A)
(⎤D→(⎤A&⎤С )).
Слайд 30
каждое вхождение логической связки “⎤” относится к пропозициональной
переменной или формуле, следующей непосредственно за логической связкой справа;
каждое
вхождение логической связки “&” после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие логическую связку;
каждое вхождение логической связки “∨” после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие эту связку и т.д.;
в формулах нет двух рядом стоящих логических связок - они должны быть разъединены формулами;
в формулах нет двух рядом стоящих формул - они должны быть разъединены логической связкой.
логические связки по силе и значимости упорядочены так: ⎤, &, ∨, →, ↔, т.е. самая сильная связка - отрицание, затем коньюнкция, дизьюнкция, импликация и, наконец, эквиваленция; знания о силе логических связок позволяют опускать скобки, без которых ясен порядок исполнения логических операций.
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Слайд 31
Пример.
Пусть дана формула F = (((F1∨(⎤F2))→F3)↔F4).
1. Убрать
внешние скобки для формулы, так как они не определяют
старшинство никаких операций: F = ((F1∨(⎤F2))→F3)↔F4;
2. Убрать скобки, охватывающие формулу импликации, так как операция эквиваленции будет исполняться только после выполнения операции импликации: F = (F1∨(⎤F2))→F3↔F4;
3. Убрать скобки, охватывающие формулу дизъюнкции, так как операция импликации будет исполняться только после выполнения операции дизъюнкции: F = F1∨(⎤F2)→F3↔F4;
4. Убрать скобки, охватывающие формулу отрицания, так как операция дизъюнкции будет исполняться только после выполнения операции отрицания:
F=F1∨⎤F2→F3↔F4;
Итак, последовательность исполнения операций после задания значений пропозациональных переменных следующая:
сначала определить значение формулы (⎤F2), затем (F1∨(⎤F2)) затем ((F1∨(⎤F2))→F3) и, наконец, (((F1∨(⎤F2))→F3)↔F4).
ПРАВИЛА ЗАПИСИ СЛОЖНЫХ ФОРМУЛ
Слайд 32
Две формулы F1 и F2 называются равносильными, если
они имеют одинаковое значение “и” или “л” при одинаковых
наборах пропозициональных переменных, включаемых в F1 и F2, т.е. F1 = F2 .
Если две формулы равносильны, то они эквивалентны, т.е. (Fi↔Fi).
Если формула F имеет вхождением подформулу Fi, для которой существует эквивалентная подформула Fj, т.е. Fi↔Fj, то возможна подстановка всюду в формулу F вместо формулы Fi подформулы Fj без нарушения истинности формулы F.
Подмножество эквивалентных формул для преобразований сложных логических суждений формируют законы алгебры высказываний.
ЗАКОНЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ
Таблица законов алгебры высказываний
Слайд 33
ТАБЛИЦА ЗАКОНОВ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ
Слайд 34
Пример: F1∨(F1&F2) = F1
Сравните значения логических функций в
третьем и четвертом столбцах. Так можно проверить первый закон
поглощения.
Пример: ⎤(F1∨F2) = ⎤F1&⎤F2
Сравните значения логических функций в третьем и четвертом столбцах. Так можно проверить первый закон де Моргана.
ЗАКОНЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ
Слайд 35
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
Знание законов алгебры высказываний позволяет выполнять
эквивалентные преобразования любых логических формул, сохраняя их значения для
любых наборов пропозициональных переменных. Ниже на примерах рассмотрены эквивалентные преобразования основных логических операций.
Пример: F1→F2 = ⎤F1∨F2 = ⎤(F1&⎤F2).
Сравните значения логических функций в третьем, четвертом и пятом столбцах. То есть операцию импликации всегда можно заместить исполнением операций дизьюнкции и отрицания или коньюнкции и отрицания.
Слайд 36
Пример: F1↔F2 = ⎤F1&⎤F2∨F1&F2 = ⎤(⎤(⎤F1&⎤F2)&⎤(F1&F2)).
Сравните значения логических
функций в третьем, шестом и восьмом столбцах. Это значения
трех эквивалентных функций.
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
Слайд 37
Выполненные примеры показывают, что всякую формулу алгебры логики
можно заместить равносильной ей формулой, содержащей вместо импликации или
эквиваленции только две логических операции: дизьюнкцию и отрицание или коньюнкцию и отрицание.
Этот факт показывает, что множество логических связок дизъюнкции и отрицания, конъюнкции и отрицания формируют функционально полные алгебраические системы. Они достаточны для выражения любой логической функции, любой таблицы истинности.
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
Слайд 38
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
ПРАВИЛА ЗАМЕНЫ И ПОДСТАНОВКИ
Правило замены.
Если
формула F содержит подформулу Fi, то замена подформулы Fi
в формуле F на эквивалентную ей формулу Fj не изменяет значения формулы F при любом наборе пропозициональных переменных.
Правило подстановки.
Если необходима подстановка в формулу F вместо формулы Fi новой формулы Fj , то эту операцию нужно выполнить всюду по символу Fi .
Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.
Слайд 39
Пример: Дано F =⎤(F1→F2)&(⎤F3∨⎤F4)∨⎤(F1∨F2)&⎤(F3&F4).
Выполнить эквивалентные преобразования для
упрощения алгебраического выражения.
Преобразования:
1) Удалить логическую связку “→”:
F = ⎤(⎤F1∨F2)&(⎤F3∨⎤F4)∨⎤(F1∨F2)&⎤(F3&F4);
2) Опустить отрицание на элементарные формулы по закону де Моргана:
F = F1&⎤F2&(⎤F3∨⎤F4)∨ ⎤ F1&⎤F2&(⎤F3∨⎤F4);
3) Выполнить преобразование по закону дистрибутивности:
F = ( F1∨⎤ F1) &⎤F2&(⎤F3∨⎤F4);
4) Удалить член ( F1∨⎤F1) = и:
F =⎤F2&(⎤F3∨⎤F4).
Дальнейшее упрощение формулы F невозможно.
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
ПРАВИЛА ЗАМЕНЫ И ПОДСТАНОВКИ
F1→F2 = ⎤F1∨F2 = ⎤(F1&⎤F2).
Слайд 40
Пример: Дано суждение "или верно, что Петр поступил
в университет (А), и при этом неверно, что Петр
не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)".
Формула сложного высказывания имеет вид:
А&⎤(⎤A&⎤В)∨А&С∨А&В&С;
1) преобразовать, используя закон де Моргана:
А& (А∨В)∨А&С∨А&В&С;
2) применить закон идемпотентности:
А& (А∨В)∨A&А&С∨А&В&С;
3) применить закон дистрибутивности по переменной А:
А&((А∨В)∨ А&С∨В&С);
4) применить закон дистрибутивности по переменной С:
А&((А∨В)∨ С&(А∨В));
5) ввести константу "и":
А&((А∨В)&”и”∨ С&(А∨В));
6) применить закон дистрибутивности для подформулы (А∨В):
А&(А∨В)&(“и”∨С);
7) удалить (“и”∨С):
А&(А∨В);
8) применить закон поглощения: А.
Следовательно, в данном высказывании утверждается только то, что Петр поступил в университет, а об Андрее и Семене никакой информации нет.
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ
ПРАВИЛА ЗАМЕНЫ И ПОДСТАНОВКИ
Слайд 41
ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Определение исчисления высказываний, как и любой
формальной системы, следует начинать с задания множества аксиом и
правил вывода, обеспечивающих последовательное их использование при доказательстве истинности заключения.
Доказательство - конечная последовательность высказываний, каждое из которых является либо аксиомой, либо выводится из одного или более предыдущих высказываний этой последовательности по правилам вывода.
Определение минимально возможного множества аксиом определяет семантическую полноту исчисления, а определение правил, обеспечивающих последовательное использование аксиом и промежуточных высказываний в процессе формирования заключения – метод дедуктивного вывода.
Слайд 42
Если дана некоторая формула F и каждой ее
пропозициональной переменной приписано значение "и" или "л", то говорят
что дана интерпретация формулы F.
Все множество формул логики высказываний можно разбить на три класса: тождественно истинные, тождественно ложные и теоремы. В каждом классе может быть перечислимое и счетное множество формул.
Тождественно истинные формулы (общезначимые) – особый класс формул, которые принимают значение “истины” при любом значении пропозициональных переменных, входящих в эту формулу. Эти формулы играют роль аксиом и законов логики высказываний.
Тождественно ложные формулы (противоречия) - особый класс формул, которые принимают значение “ложь” при любых значениях пропозициональных переменных, входящих в формулу.
Выполнимые формулы - это особый класс формул, которые принимают значения “истина” или “ложь” в зависимости от значений пропозициональных переменных.
Поиск алгоритма, определяющего к какому классу принадлежит та или иная формула, формирует проблему разрешимости исчисления высказываний.
ИНТЕРПРЕТАЦИЯ ФОРМУЛ
Слайд 43
F = ((A→B)&(A→C)→(A→(B&C))
Формула принадлежит классу тождественно истинных
формул (см. столбец 9).
ИНТЕРПРЕТАЦИЯ ФОРМУЛ
Какому классу принадлежит формула:
Слайд 44
F=A& (⎤B∨⎤C) &(A→B) & (A→C)
Формула принадлежит классу тождественно
ложных формул (см. столбец 9).
ИНТЕРПРЕТАЦИЯ ФОРМУЛ
Какому классу принадлежит формула:
Слайд 45
АКСИОМЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Множество формул, удовлетворяющих условиям тождественной истинности,
бесконечно. Однако в качестве аксиом всегда выбирают только такие,
которые при истинности посылок обеспечивают дедуктивный вывод истинности заключения. При этом стремятся создать такую систему аксиом, которая содержала бы минимальное число формул для заданного набора логических связок.
А1. F1→(F2→F1);
А2. (F1→F2)→((F2→F3))→(F1→F3));
А3. (F1& F2)→F1;
А4. (F1& F2)→F2;
А5. F1→(F2→(F1&F2));
А6. F1→(F1∨F2);
А7. F2→(F1∨F2);
А8. (F1→F3)→((F2→F3)→((F1∨F2)→F3));
А9. (F1→F2)→(( F1→⎤ F2)→⎤ F1);
A10. (F1→F2)→((F1&F3)→(F2&F3));
A11. (F1→ F2)→((F1∨F3)→(F2∨F3));
А12. ⎤⎤ F1 → F1.
Слайд 46
А2. (F1→ F2)→(( F1→( F2→ F3))→( F1→ F3))
А8.
(F1→ F3)→(( F2 → F3)→(( F1 ∨ F2)→ F3))
ИНТЕРПРЕТАЦИЯ
ФОРМУЛ
Слайд 47
ПРАВИЛА ВЫВОДА
Выводом формулы В из множества формул F1
, F2 ,. . ., Fn называется такая последовательность
формул, что любая Fi есть либо аксиома, либо непосредственно выводима из подмножества предшествующих ей формул F1, F2, . . . , Fn.
В этом случае формулу B называют заключением, а последовательность формул F1; F2; . . . Fn, сформированная отношением логического вывода, представляет схему дедуктивного вывода.
Схему дедуктивного вывода записывают так:
F1; F2; . . . Fn |⎯ B,
где символ |⎯ означает «верно, что B выводима из F1, F2,... ,Fn».
Есть определенная связь между отношением логического вывода в схеме дедуктивного вывода и импликацией в схеме закона алгебры высказываний .
Этот факт записывают так:
|⎯ F1&F2&. . . &Fn→B.
Слайд 49
Пример: пусть даны формулы F = A&C →
A и B = C → ⎤A.
Проверим значения
двух формул F и F’ по таблицам истинности. Выделенные столбцы показывают тождество двух формул.
ПРАВИЛА ПОДСТАНОВКИ
Если выполнить подстановку формулы B в формулу F вместо формулы A,
то получим новую формулу F`.
Слайд 50
П1. Если посылки F1 и F2 имеют значение
“и”, то истинной является их конъюнкция, т.е.
Эта запись при
истинности посылок F1 и F2 предусматривает возможность введения в заключение логической связки конъюнкции; это правило тождественно аксиоме А5;
П2. Если (F1&F2) имеет значение “и”, то истинными являются подформулы F1 и F2, т.е.
Эта запись при истинности (F1&F2) предусматривает возможность удаления в заключении логической связки конъюнкции и рассматривать истинные значения подформул F1 и F2; это правило тождественно аксиомам А3 и А4;
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
1
Слайд 51
П3. Если F1 имеет значение “и”, а (F1&F2)
– “л”, то ложной является подформулы F2, т.е.
Эта запись
при ложности (F1&F2) и истинности одной из подформул предусматривает возможность удаления в заключении логической связки конъюнкции и рассматривать ложным значение второй подформулы;
П4. Если истинна хотя бы одна посылка F1 или F2, то истинной является их дизъюнкция, т.е.
Эта запись при истинности хотя бы одной подформулы F1 или F2 предусматривает возможность введения в заключение логической связки дизъюнкции; это правило тождественно аксиомам А6 и А7;
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 52
П5. Еесли (F1∨F2) имеет значение “и” и одна
из подформул F1 или F2 имеет значение “л”, то
истинной является вторая подформула F2 или F1, т.е.
Эта запись при истинности (F1∨F2) предусматривает возможность удаления в заключении логической связки дизъюнкции и рассматривать истинные значения подформул F1 или F2;
П6. Если подформула F2 имеет значение “и”, то истинной является формула (F1→F2) при любом значении подформулы F1, т.е.
Эта запись при истинном значении F2 предусматривает возможность введения в заключение логической связки импликации при любом значении подформулы F1 (“истина из чего угодно”); это правило тождественно аксиоме А1.
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 53
П7. Если подформула F1 имеет значение “л”, то
истинной является формула (F1→F2) при любом значении подформулы F2,
т.е.
Эта запись при ложном значении F1 предусматривает возможность введения в заключение логической связки импликации при любом значении подформулы F2 (“ из ложного что угодно”);
П8. Если формула (F1→F2) имеет значение “и”, то истинной является формула (⎤F2→⎤F1), т.е.
Эта запись при истинном значении (F1→F2) определяет возможность замены местами полюсов импликации при одновременном изменении их значений; это - закон контрапозиции;
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 54
П9. Если формула (F1→F2) имеет значение “и”, то
истинной является формула ((F1∨F3)→(F2∨F3) при любом значении F3, т.е.
Эта
запись при истинном значении (F1→F2) определяет возможность выполнить операцию дизъюнкции при любом значении формулы F3 над каждым полюсом импликации; это правило тождественно аксиоме А11.
П10. Если формула (F1→F2) имеет значение “и”, то истинной является формула ((F1&F3)→(F2&F3) при любом значении F3, т.е.
Эта запись при истинном значении (F1→F2) определяет возможность выполнить операцию конъюнкции при любом значении формулы F3 над каждым полюсом импликации; это правило тождественно аксиоме А10.
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 55
П11. Если формулы (F1→F2) и (F2→F3) имеют значение
“и”, то истинной является формула (F1→F3), т.е.
Эта запись при
истинном значении (F1→F2) и (F2→F3) предусматривает возможность формирования импликации (F1→F3) (закон силлогизма);
это правило тождественно аксиоме А2;
П12. Если формулы F1 и (F1→F2) имеют значение “и”, то истинной является формула F2, т.е.
Эта запись при истинном значении посылки F1 и импликации (F1→F2) позволяет удалить логическую связку импликации и определить истинное значение заключения F2;
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 56
П13. Если формулы ⎤F2 и (F1→F2) имеют значение
“и”, то истинной является формула ⎤F1, т.е.
Эта запись при
истинном значении посылки ⎤F2 и импликации (F1→F2) позволяет удалить логическую связку импликации и определить истинное значение заключения ⎤F1;
П14. Если формулы (F1→F2) и (F2→F1) имеют значение “и”, то истинной является формула (F1↔F2), т.е.
Эта запись при истинном значении (F1→F2) и (F2→F1) позволяет ввести логическую связку эквиваленции и определить значение формулы (F1↔F2);
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 57
П15. Если формула (F1↔F2) имеет значение “и”, то
истинными являются формулы (F1→F2) и (F2→F1), т.е.
Эта запись при
истинном значении (F1↔F2) позволяет удалить логическую связку эквиваленции и определить истинное значение формул (F1→F2) и (F2→F1).
ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ ЛОГИЧЕСКИХ СВЯЗОК
Слайд 58
ПРАВИЛА ЗАКЛЮЧЕНИЯ
а) если Fi и ( Fi →
Fj ) есть выводимые формулы, то Fj также выводимая
формула, т.е.
b) если формулы ⎤Fj и (Fi→Fj) есть выводимые формулы, то ⎤Fi также выводимая формула, т.е.
это правило называют modus tollens (m.t.).
При выводе формулы из множества аксиом и посылок используют два основных правила:
это правило называют modus ponens (m.p.).
Слайд 59
Пример: суждение: “Сумма внутренних углов многоугольника равна 180о
(А). Если сумма внутренних углов многоугольника равна 180о (A),
то многоугольник есть треугольник (В). Следовательно, дан треугольник”.
Пример: суждение: ”Дан не треугольник (⎤B); если сумма внутренних углов многоугольника равна 180о(А), то многоугольник есть треугольник (В). Следовательно, сумма внутренних углов многоугольника не равна 180о(⎤A)”.
ПРАВИЛА ЗАКЛЮЧЕНИЯ
Слайд 60
МЕТОД ДЕДУКТИВНОГО ВЫВОДА
Теорема F1, F2 ,..., Fn |⎯
В равносильна доказательству |⎯ (F1&F2&...&Fn→B ). Если каждая Fi
= и, то F1& F2&...&Fn ) = и, а если (F1&F2&...&Fn→B) = и, то В = и.
Следовательно, при истинности всех посылок и истинности импликации (правило m.p.), заключение всегда будет истинным.
Используя правила эквивалентных преобразований алгебры высказываний, можно показать дедуктивный характер вывода заключения:
1) |⎯ (F1&F2&...&Fn→B);
2) |⎯ (⎤(F1&F2&...&Fn )∨B);
3) |⎯ (⎤F1∨⎤F2 ∨...∨⎤Fn∨B);
4) |⎯ (⎤F1∨⎤F2 ∨...∨⎤Fn-1∨(Fn→B));
5) |⎯ (⎤F1∨⎤F2 ∨...∨(Fn-1→ (Fn→B)));
6) |⎯ (⎤F1∨(F2 →...→ (Fn-1→ (Fn→B))...));
7) |⎯ (F1→(F2 →...→ (Fn-1→ (Fn→B))...)
Так формируется система дедуктивного вывода от посылок до заключения.
Слайд 61
Пример. Дано cуждение: “Всякое общественноопасное деяние (А) наказуемо
(В). Преступление (С) есть общественно опасное деяние (А). Дача
взятки (D) - преступление (C). Следовательно, дача взятки наказуема ?”.
1) F1=A→B посылка;
2) F2=С→А посылка;
3) F3=D→C посылка;
4) F4=C→B заключение по формулам F1 и F2 и аксиоме А2 или правилу 11;
5) F5=D→B заключение по формулам F3 и F4 и аксиоме А2 или правилу 11.
Следовательно, дача взятки (D) наказуема (B).
МЕТОД ДЕДУКТИВНОГО ВЫВОДА
П 11
Слайд 62
Пример. “Если Петров не трус (A), то
он поступит в соответствие с собственными убеждениями (B). Если
Петров честен (C), то он не трус (A). Если Петров не честен ⎤(C), то он не признает своей ошибки (D). Но Петров признает свои ошибки ⎤(D). Следовательно, он поступит согласно собственным убеждениям (B)?"
1) F1=A→B посылка;
2) F2=C→A посылка;
3) F3=⎤C→D посылка;
4) F4=⎤D посылка;
5) F5=C→B заключение по формулам F1, F2 и аксиоме А2 или правилу 11;
6) F6=⎤B→⎤C заключению по формуле F5 и правилу 8);
7) F7=⎤B→D заключение по формулам F3 и F6 и аксиоме А2 или правилу 11;
8) F8=B заключение по формулам F4, F7 и правилу m.t..
Так доказано, что Петров поступает согласно собственным убеждениям.
МЕТОД ДЕДУКТИВНОГО ВЫВОДА
П 11
П 8
m.t.
Слайд 63
Пример. Доказать истинность заключения
1) F1=(A→C)
поcылка;
2) F2=(A∨B)→(C∨B)
заключение по формуле F1 и правилу 9;
3) F3=(B→D) посылка;
4) F4=(C∨B)→(C∨D) заключение по формуле F3 и правилу 9;
5) F5=(A∨B)→(C∨D) заключение по формулам F2 и F4 и правилу 11;
6) F6=(A∨В) посылка;
7) F7=(C∨D) заключение по формулам F5 и F6 и правилу m. p..
Так доказана истинность заключения (C∨D).
МЕТОД ДЕДУКТИВНОГО ВЫВОДА
Слайд 64
Пример: Доказать истинность заключения :
1) F1=((⎤ D)&(⎤ N))
посылка;
2) F2=⎤N
заключение по формуле F1 и правилу 2;
3) F3=(M→N); посылка ;
4) F4=⎤M заключение по формулам F2 и F3 и правилу m.t;
5) F5=⎤D заключение по формуле F1 и правилу 2;
6) F6=(⎤D)&(⎤M) заключение по формулам F4 и F5 и правилу 1;
7) F7=⎤(D∨М) заключение по формуле F6 и закону де Моргана;
8) F8=(( A∨B)→C) посылка;
9) F9=(С→ (D∨М)) посылка;
10) F10=((A∨B)→(D∨M)) заключение по формулам F8 и F9 и правилу 11;
11) F11=⎤(A∨B) заключение по формулам F7 и F10 и правилу m.t.;
12) F12=(⎤А)&(⎤B) заключение по формуле F11 и закону де Моргана;
13) F13=⎤A заключение по формуле F12 и правилу 2.
МЕТОД ДЕДУКТИВНОГО ВЫВОДА
Слайд 66
Алгебра, использующая операции дизъюнкции, конъюнкции и отрицания над
множеством, элементы которого принимают значения из множества {0, 1},
называется булевой алгеброй в часть английского математика Дж. Буля:
A.= < X, ∨, ⋅, , 0, 1 >,
где X – носитель алгебры, а {∨, ⋅, } - сигнатура алгебры.
Операторы конъюнкции, дизъюнкции и отрицания называют также логическими связками.
БУЛЕВА АЛГЕБРА
Слайд 67
БУЛЕВЫ ОПЕРАЦИИ
Дизъюнкция (x1∨x2) есть бинарная операция, значение которой
равно 0 в том и только в том случае,
когда оба операнда равны 0.
Схема операции имеет вид: f(xi, xj) = disjunction (хi, хj). Операцию дизъюнкции можно выполнять на произвольном числе элементов множества X. Например,
f(х1, х2,…, хn) = (х1∨х2∨...∨хn) = i =1∨n хi.
Слайд 68
БУЛЕВЫ ОПЕРАЦИИ
Конъюнкция (x1⋅x2) есть бинарная операция, значение которой
равно 1 в том и только в том случае,
когда оба операнда равны 1.
Схема операции имеет вид: f(xi, xj) = conjunct (х1, х2). Операцию конъюнкции можно выполнять на произвольном числе элементов множества X. Например,
f (х1, х2,..., хn) = (х1⋅х2⋅…⋅хn) = i =1&n хi,
Слайд 69
БУЛЕВЫ ОПЕРАЦИИ
Отрицание x есть унарная операция, значение которой
противоположно значению операнда. Схема операции имеет вид: (x) =
not(x). Операцию отрицания можно распространить на произвольные формулы булевой алгебры. Например,
f(x1,x2,...,xn) =⎤(x1∨х2∨...∨хn) = (x1∨х2∨...∨хn),
f(x1, x2,…,xn) =⎤(х1⋅х2⋅...⋅xn) = (х1⋅х2⋅...⋅xn ).
Слайд 70
ЗАКОНЫ БУЛЕВОЙ АЛГЕБРЫ
Аксиомы общей алгебры формируют законы булевой
алгебры:
коммутативности: xi∨xj = xj∨xi и xi⋅xj = xj⋅xi,
ассоциативности: xi∨(xj∨xk)
= (xj∨xj)∨xk и xi⋅(xj⋅xk) = (xj⋅xj)⋅xk,
дистрибутивности: xi∨(xj⋅xk) = (xi∨xj)⋅(xi∨xk) и xi⋅(xj∨xk) = (xi⋅xj)∨(xi⋅xk),
идемпотентности: (xi∨xi) = xi и (xi⋅xi) = xi,
поглощения: xi∨(xi⋅xj) = xi и xi⋅(xi∨xj) = xi,
противоречия: (x∨x) =1 и (x⋅x) = 0,
двойного отрицания: ⎤(x) = x,
склеивания: x⋅F∨x⋅F = F, (x∨F)⋅(x∨F) = F,
де Моргана: ⎤(xi∨xj) =xi⋅xj и ⎤(xi⋅xj) =xi∨xj,
Порецкого x∨x⋅y = x∨y, x⋅(x∨y) = x⋅y,
константы: (x∨0) = x, (x⋅0) = 0, (x∨1) = 1, (x⋅1) = x.
Слайд 71
ФОРМУЛА БУЛЕВОЙ ФУНКЦИИ
Функцию y = f(x1, x2,..xn), значение
которой и значения компонент аргумента принадлежат множеству {0, 1},
называют булевой, а аргумент – булевым вектором. Компоненты булевого вектора называют булевыми (или двоичными) переменными.
Алгебраическое выражение булевой функции, использующее только булевы переменные булевого вектора и только логические связки конъюнкции, дизъюнкции и отрицания, называют формулой.
Если даны булевы переменные xi, xj, то элементарными формулами являются F =xi, F=⎤xj, F= (xi∨xj), F = (xi⋅xj), а производными формулами F=⎤F, F = (Fi∨Fj), F = (Fi⋅Fj).
Слайд 72
ФОРМУЛА БУЛЕВОЙ ФУНКЦИИ
Для описания функции формулами используют два
правила: подстановки и замещения.
Пусть даны равносильные формулы Fi
и Fj, т. е. (Fi = Fj), которые содержат переменную x. Если всюду в формулы Fi и Fj вместо x подставить произвольную формулу F, то будут получены также равносильные между собой формулы F’i и F’j, т. е. F’i = F’j.
Пусть дана формула (Fi = Fj) и существует формула Fk, равносильная только одной подформуле Fi, т. е. (Fi = Fk). Тогда Fi может быть замещена формулой Fk и получена новая формула (Fk = Fj). При этом не обязательно ее замещение всюду в алгебраическом выражении булевой функции.
Слайд 73
ОПИСАНИЕ БУЛЕВОЙ ФУНКЦИИ
При табличном описании булевой функции необходимо
для каждого набора двоичных переменных булевого вектора указывать её
значение. Если значение функции определено не для всех наборов булевого вектора, то функцию называют частично определённой.
Число строк таблицы детерминированной функции от n компонентов аргумента равно 2n.
При аналитическом описании булевой функции используют элементарные унарные и бинарные операторы булевой алгебры, а также правила подстановки и замещения при формировании формул булевой функции.
Число логических функций для n компонентов аргумента определяется выражением: 2p, где p=2n.
