Множества. Под множеством будем понимать совокуп.каких-либо объектов произвольной природы объединенных некот.общим св-ом.

Множества. Под множеством будем понимать совокуп.каких-либо объектов произвольной природы объединенных некот.общим св-ом.

Способы задания множеств: а)Словестный, б)Перечислением всех элементов мн-ва, в)Указанием основного признака, г)Геометрически

Виды множеств: Множество натуральных чисел-числа кот.использ-я при счете.

Целые числа-числа натуральные, им противоположные и 0. (-10эZ)

Множ-во Рациональных чисел-число вида дробь: m/n где m э Z, а n э N (0.7 э Q:)

Мн-во Иррациональных-число кот.не явл-ярациональным. (-17.3333355 э J)

Мно-во Действительных чисел-числовое мн-во образов.множеством рациональнм и иррациональным множ-вом (R).

 

3) Операции над множествами: а) Пересечение мн-в. Пересечением множеств А и В назыв.множ-во сост.из тех и только тех элементов,которые принадлежат одновременно и А и В.

Универсальным множеством называется множество состоящее из всех возможных элементов удовлетворяющих характеристич-у св-ву множеств. (U).

Дополнением к множеству А называют множество, состоящее из тех и только тех элементов, кот. не принадлежат множеству А.

 

5) Мощность и классификация множеств. Мощность множества-количество элементов множества |М|.

Два множества называют-я равными, если они составлены из одинаковых елементов.

Два множества назыв-я эквивалентными, если между их элементами можно установить взаимно-однозна-е соответсвие.

Синонимом эквивалентности множеств-явл-я равномощное множество.

Конечное множество. Конечное-если оно содержит конечное число элементов(конкретное число) пустое, студ.гр.АС1-21

Беконечное-множество-не явл-я конечным. Оно бывает: Счетное-если оно эквивалентно множ-ву натуральных чисел. (N, Z, Q)

Несчетное-бесконечное множ-во явл-я счетным. (R, J)

 

Под формулой АЛГЕБРЫ ЛОГИКИ будем понимать выражение состав-х из символов высказыв-х переменные,элементов высказываний, логич.операций и символов расстановки скобок

Если в формулу А/Л вместо переменной подставить элемен-е высказыв-е, то формула станет составным высказыванием.

 

Формула А/Л называется ТОЖДЕСТВЕННО-ИСТИННОЙ(тавтологией) если оно принимает значения истина при любых значениях входящих в нее переменных.(в посл.столбце-одни единицы)

Формула А/Л называется ТОЖДЕСТВЕННО-ЛОЖНОЙ если оно принимает значения ложь при любых значениях входящих в нее переменных.(в посл.столбце-одни нули)

Формула А/Л назыв. ВЫПОЛНИМОЙ(опровержимой)если найдется такой набор значений входящих в нее переменных, что на этом наборе формулапринимает значения истина(ложь)(в посл.столбце на ряду с единицами присутствуют нули)

 

17) Таблица истинности представляет собой прочный теоретический фундамент на кот.осно.многие технич-е проекты.

Елементарной конъюкцией(дизъюнкицей) называется формула из конечного числа переменных либо отрицаний,встречающихся в формуле не более одного раза, и разделенных между собой логической операцией конъюнкцией(дизъюнкцией)

Дизъюнктивной Нормальной Формы называется дизъюнкия конечного числа элементарных конъюнкций.

Нормальная форма называется совершенной,если в каждой ее элементарной конъюнкции(дизъюнкции) представлены все переменные формулы либо сами,либо своими отрицаниями.

 

Конъюнктивной нормальной формы-называется конъюнкция конечного числа элементарных дизъюнкций.

20) Всех законы-в таблице.

21) Две формулы А/Л называются равносильными если они принимают одинаков.логич.значения при соответств-х наборах значениях переменных этих формул.

А/Л будут равносильны, если соответствующии столбцы таблицы истинности будут одинаковыми. (f1=f2)

 

Булевой функцией n-переменных назыв.-отображение n-ой декартовой степени множества В во множество В сопоставл-е по определенному правилу каждой n-ке из 0 и 1 единственное значение из множества В

Способы задания: а) Таблица знаний булевой функции n переменных называется таблица сост. Из 0 и 1, содержащая 2в степени n строк и n+1 столбец, и позволяющая найти знач-е булевой функции.

б) Булевым вектором Б.Ф n-переменных называется вектор состоящий из К координат.

в) Геометрически.

Г) Аналитически.(формулой). Основной задачей явл-я задача предствавления Б.Ф формулой,содерж конкретное число,наперед заданных элементарных Б.Ф

23) Б.Ф одной переменной называется тождевст-0(1) если при любом знач.арг.принимает знач=0 или 1.

Б.Ф 1 переменной называется тождевственной, елси она принимает значении,совпадающие со своим аргументом.

Б.Ф 2 переменных называется дизъюнкцией, если она принимает значения=0 в том случ.когда оба ее аргумента обращ в 0.

Б.Ф 2 переменных называется конъюнкцией если она принимает значения =1 в том, случ.когда обе ее переменных принимают знач=1

Б.Ф 2 переменных называется эквиваленцией,если она принимает значения=1 в том случ, когда переменные принимают совпад значения.

Б.Ф 2 переменных называются импликацией из х в у если она принимает значения =0, в том случае если первая переменная=1 а вторая=0

Б.Ф 2 переменных назыв.Суммой по модулю 2,если она принимает знач=1 в том случ,когда ее переменная приним.несовпадающие знач-я.

Б.Ф 2 переменных называется штрихом Шеффера,если она принимает значения=1, в том случ,когда обе переменные обращ в 1.

Б.Ф 2 переменных называется стрелкой Пирса,если она принимает знач=1, в том случ.когда обе переменные обращ. В 0

 

Реализация Б.Ф. Любая Б.Ф отличная от тождевственного 0(тожд.1) представима однозначно в виде СДНФ(СКНФ)

Алгоритм СДНФ: а) Задать таблицу. б) Выделить в таблице те строки знач.кот=1,

в) Для кажд.из выдел строк,выписать конституенты 1 г) Для кажд констит 1 составить элементар.конъюнкию если 1-сама по себе, 0-своим отрицанием. К альфа=()

25) тоже, только нули подчеркиваем, 0-сама по себе, 1-отрицанием.

26) Свойства Суммы по модулю 2: а) Коммутативна х+у=у+х б) ассоциативна (х+у)+z=х+(у+z)

в) Конъюнкция дистрибутивна относит. Сумм по мод 2 X(y+z)=XY+XZ

г) Х+Х=0 д) Х+0=Х е)Х+1=отриц.Х д)Х+отрХ=1 ж)х+у+ху=х v у

27) Многочлен Жегалкина! Многочлен жегалкина представляет собой композицию трехбулев.функций(конъюн,+,тожд1)!

Теорема:Любая Б.Ф представима причем однозначно многочленом Жегалкина(через конъюн,+,тожд1)

28) Функционлано замкнутые классы: Функционально замкнутым классом Б.Ф назыв.класс(подмножества)Б.Ф, таких что композиция любого числа Б.Ф из данного класса-этому-же классу и принадлежит.

Классы: Т0-сохраняющей константу 0 (тождевст.0,дизъюнкция); Т1-сохран.константу 1(тожд.1, конъюнкция); L-класс линейных Б.Ф(имплицакия)

S-класс самодвойственной Б.Ф. М-класс монотонных Б.Ф.

29) Б ,Ф n-переменных называется сохран.константу 0,если на нулевом наборе знач переменных Б.Ф принимает значения=0. F(x,y)=X v Y: F(00)=0 v 0=0, FэT0

Если Б.Ф задана булевым вектором и первая координата вект=0, то б.ф сохран.конст0 в противном случае перв.координата=1, не сохран.конст0.

30) Б,Ф n-переменных называется сохраняющей конст.1 если на единичном знач наборе знач.переменных б.ф будет принимать значения=1. F(X*Y)=X*Y: F(11)=1*1=1 значит FэT1

31 ) Б,Ф n-переменных называется линейной, если она представима многочленом Жегалкина, степени не выше первой(0 или1) (х+у).

32) Монотонной б.Ф n-переменных назыв.б.ф для кот, для каждых двух сравнимых между собой ее аргументов из того, что первый арг.предш.второму, значение б.ф на первом арг.предшест.знач.б.ф на второй. (0*0)<(0*1) (0*0)<(1*0) (1*1)не меньше!(00)

Б.Ф –переменных называются двойственными,если на противоположных значениях,они принимают противополож.значения.

Б.Ф n-переменных назыв.самодвойственной если она двойственна сама себе.

34)Система Б.Ф называется функционально полной если любую б.ф можно представить в виде композиции определенного набора б.ф этой системы.(СНФ) {*, V,-}, {+,*,1}

35) Теорема ПОСТА: Для того чтобы система б.ф была функционально полной необходимо и достаточно чтобы для каждого из классов Поста в сисеме нашлась функция не принадлежащая ему. (используем таблицу ПОСТА). Число столбцов=5,число строк-количество б.ф!

Элементы теории Графов. ГРАФ-пара двух конечных множеств множества точек и множество линий соединенных некот.пары точек. G(V,X) где V-множ.точ. Х-множ.линий.

Графы бывают: Неориентированные, и Ориентированные.

Способы задания графов: а) Геометрически(диаграммой) б) Матрицей инцидентности

в) Матрицей смежности. г) Простым перечислением его вершин и ребер(дуг)

Множества. Под множеством будем понимать совокуп.каких-либо объектов произвольной природы объединенных некот.общим св-ом.

Способы задания множеств: а)Словестный, б)Перечислением всех элементов мн-ва, в)Указанием основного признака, г)Геометрически

Виды множеств: Множество натуральных чисел-числа кот.использ-я при счете.

Целые числа-числа натуральные, им противоположные и 0. (-10эZ)

Множ-во Рациональных чисел-число вида дробь: m/n где m э Z, а n э N (0.7 э Q:)

Мн-во Иррациональных-число кот.не явл-ярациональным. (-17.3333355 э J)

Мно-во Действительных чисел-числовое мн-во образов.множеством рациональнм и иррациональным множ-вом (R).

 

3) Операции над множествами: а) Пересечение мн-в. Пересечением множеств А и В назыв.множ-во сост.из тех и только тех элементов,которые принадлежат одновременно и А и В.