Математикалык логика негіздері

Математикалык логика – дөлелдеулер техникасын зерттейді. Компьютерлер математика пәні сиякты аныктамалар мен дәлелдеулерде нақтылықты және қатаң реттілікті талап етеді.

Пікірлер алгебрасы математикалық логика аймағы болып табылады.

Пікірлер алгебрасы —идеал пікірлерге қатысты ақиқат немесе жалған пікір деп тұжырымдауға болатын пікірлерді зерттейтін логикалар алгебрасы. Логикалар алгебрасы пікірдің мағынасына назар аударып, терең қарастырмайды.

Сондықтан логикалар алгебрасы тек екі мағынаға ие болады, яғни пікірлердің кез келгені «акикат» немесе «жалған» пікірлерінің біреуін ғана сипаттайды.

Вы уже знаете о суперспособностях современного учителя?

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

Быстро и объективно проверять знания учащихся.

Сделать изучение нового материала максимально понятным.

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«Математикалык логика негіздері»

Логика алгебрасының функциялары.

Логика заңдары

Логикалық функция

Логикалық функция – бұл x 1 ,x 2 ,…,x n логикалық айнымалылар жиынтағында 0 және 1 мәндерін қабылдайтын f ( x 1 ,x 2 ,…,x n ) функциясы.

Берілу тәсілдері

Логикалық алгебра өрнегі

f ( x 1 , x 2 , x 3 ) = x 1 + x 2 *  x 3

Ақиқаттық кестесі

Логикалық схемасы

х 1

х 2

х 3

f ( x 1 , x 2 , x 3 )

х 1

x 1 + x 2 *  x 3

х 2

 х 3

х 3

Күрделілігі әртүрлі кез келген логикалық функцияны негізгі логикалық функциялар деп аталатын үш функция арқылы суреттеуге болады, олар – ЕМЕС, НЕМЕСЕ, ЖӘНЕ функциялары.

Олардың атқарар қызметін кесте түрінде (ол ақиқаттық кестесі деп аталады) немесе сәйкесті логикалық өрнек арқылы суреттеуге болады.

ЕМЕС функциясы

ЕМЕС функциясы – аргументіне қарсы мәнді шығаратын, бір аргументті функция (1.1-кесте), сондықтан бұл функция инверсия (inversion — терістеу) деп те аталады. Оның аргументі Х деп белгіленген болса, онда бұл функция Y= өрнегімен суреттеледі.

Х1

Логикалық теріске шығару (инверсия) аргумент үстінде сызықшамен белгіленеді. Бұл бір айнымалының функциясы:

Екі айнымалы үшін ақиқаттық кестенің түрі төмендегідей болады:

x 1

x 2

f(x 1 ,x 2 )

НЕМЕСЕ функциясы

НЕМЕСЕ функциясы – аргументтерінің барлығы да 0 кезінде ғана 0 шығаратын, ал қалған жағдайда (яғни, аргументтерінің кем дегенде біреуінің мәні 1 болғанда) 1 шығаратын, бірнеше аргументті функция (1.2-кесте). Бұл функция дизъюнкция (disjunction) немесе логикалық қосу (logical addition) деп те атала береді. Оның логикалық өрнегі Х1Х0 түрінде суреттеледі

Х1

Х0

Х1Х0

$Логикалық көбейту (конъюнкция). Бұл бірнеше айнымалының функциясы. Функция келесі түрде белгіленеді: f(x 1 x 2 ) = x 1 /\ x 2 /\ х 3 …$

Логикалық көбейту (конъюнкция). Бұл бірнеше айнымалының функциясы. Функция келесі түрде белгіленеді:

f(x 1 x 2 ) = x 1 /\ x 2 /\ х 3 …

Екі айнымалы үшін ақиқаттық кестенің түрі төмендегідей болады:

x 1

x 2

f(x 1 ,x 2 )

ЖӘНЕ функциясы

ЖӘНЕ функциясы – аргументтерінің барлығы да 1 кезінде ғана 1 шығаратын, ал қалған жағдайда (яғни, аргументтерінің кем дегенде біреуінің мәні 0 болғанда) 0 шығаратын бірнеше аргументті функция (1.3-кесте). Бұл функция конъюнкция (conjunction) немесе логикалық көбейту (logical multiplication) деп те атала береді. Оның логикалық өрнегі Х1Х0 (немесе Х1Х0) түрінде суреттеледі

Х1

Х0

Х1Х0

Логикалық қосу (дизъюнкция). Бұл бірнеше айнымалының функциясы. Функция келесі түрде белгіленеді:

f(x 1 ,x 2 ) = x 1 V x 2 V x 3 …

Суреттелген ЕМЕС , НЕМЕСЕ , ЖӘНЕ функциялары арқылы кез келген күрделі функцияны суреттеуге болады, сондықтан, олар логикалық функциялардың түпнегіздік жинағын (core set) құрады.

Цифрлық құрылғылардың схемаларын құру барысында оларды суреттеуші логикалық фунцияларды әртүрлі мақсатқа сай (мысалы, оларды қарапайым түрге келтіру үшін) түрлендіру қажет болады. Бұндай түрлендірімдер логика алгебрасының заңдары мен осы заңдардың жеке жағдайларға тікелей пайдалануға ыңғайландырып шығарылған заңдылықтарының негізінде жүргізіледі

$Шеффер функциясы Шеффер функциясы – кері көбейтуді жүзеге асырады. Белгілену: x 1  x 2 = x 1 /\ x 2 Шеффер функциясы – теріске шығарып көбейтуді орындайды. Бұл бірнеше айнымалының функциясы. Екі айнымалы үшін ақиқаттық кестенің түрі болады: Ақиқаттық кестесі Графикалық белгіленуі х 0 у 0 0 1 1 1 1 1 0 1 1 0 & х y$

Шеффер функциясы Шеффер функциясы – кері көбейтуді жүзеге асырады. Белгілену: x 1  x 2 = x 1 /\ x 2

Шеффер функциясы – теріске шығарып көбейтуді орындайды. Бұл бірнеше айнымалының функциясы. Екі айнымалы үшін ақиқаттық кестенің түрі болады:

Ақиқаттық кестесі

Графикалық белгіленуі

Пирс функциясы

Пирс функциясы логикалық кері қосуды жүзеге асырады. Белгілену: x 1  x 2 = x 1  x 2

Ақиқаттық кестесі

Графикалық белгіленуі

mod 2 бойынша қосу

XOR логикалық операцияны орындайды .

Ақиқаттық кестесі

Графикалық белгіленуі

x  y

$Логикалық алгебраның негізгі заңдары 1. Ауыстырымдылық заңы. Коммутативтілік (лат. – ауыстыру) – бұл логикалық амал келесі түрде болады: X 1 \/ X 2 = X 2 \/ X 1 X 1 /\ X 2 = X 2 /\ X 1 Егер түйін қатарлары 0 мен1 аралығында жатса, онда логикалық амал коммутативті болып табылады (теңдік символы әрдайым бірдей болса ғана). *€{˄, ˅, +, =, ׀ , ↓}$

Логикалық алгебраның негізгі заңдары

1. Ауыстырымдылық заңы.

Коммутативтілік (лат. – ауыстыру) – бұл логикалық амал келесі түрде болады:

X 1 \/ X 2 = X 2 \/ X 1 X 1 /\ X 2 = X 2 /\ X 1

Егер түйін қатарлары 0 мен1 аралығында жатса, онда логикалық амал коммутативті болып табылады (теңдік символы әрдайым бірдей болса ғана).

*€{˄, ˅, +, =, ׀ , ↓}

$2. Қосылу заңы. Ассоциативтілік (лат. – біріктіру ) X 1 \/ (X 2 \/ X 3 ) = (X 1 \/ X 2 ) \/ X 3 X 1 /\ (X 2 /\ X 3 ) = (X 1 /\ X 2 ) /\ X 3$

2. Қосылу заңы. Ассоциативтілік (лат. – біріктіру )

X 1 \/ (X 2 \/ X 3 ) = (X 1 \/ X 2 ) \/ X 3

X 1 /\ (X 2 /\ X 3 ) = (X 1 /\ X 2 ) /\ X 3

$3. Тарату заңы. Дистрибутивтілік. X 1 /\ (X 2 \/X 3 ) = (X 1 /\ X 2 ) \/(X 1 \/ X 3 ) X 1 \/ (X 2 /\ X 3 ) = (X 1 \/ X 3 ) /\ (X 1 \/ X 3 ) 4. Шағылысу заңы. X 1 \/ (X 1 /\X 2 ) = X 1 X 1 /\(X 1 \/ X 2 ) = X 1 5. Жабыстыру заңы. X 1 X 2 \/ X 1 X 2 ) = X 1 X 1 X 2 \/ X 1 X 2 ) = X 1 (X 1 \/ X 2 )(X 1 \/ X 2 ) = X 1 (X 1 \/ X 2 )(X 1 \/ X 2 ) = X 1$

3. Тарату заңы. Дистрибутивтілік.

X 1 /\ (X 2 \/X 3 ) = (X 1 /\ X 2 ) \/(X 1 \/ X 3 )

X 1 \/ (X 2 /\ X 3 ) = (X 1 \/ X 3 ) /\ (X 1 \/ X 3 )

4. Шағылысу заңы.

X 1 \/ (X 1 /\X 2 ) = X 1 X 1 /\(X 1 \/ X 2 ) = X 1

5. Жабыстыру заңы.

X 1 X 2 \/ X 1 X 2 ) = X 1 X 1 X 2 \/ X 1 X 2 ) = X 1

(X 1 \/ X 2 )(X 1 \/ X 2 ) = X 1 (X 1 \/ X 2 )(X 1 \/ X 2 ) = X 1

$6. Де Морган ережесі. X 1 \/ X 2 \/X 3 = (X 1 /\ X 2 /\X 3 X 1 /\X 2 /\ X 3 = X 1 \/X 2 \/ X 3 ) 7. Жойылу заңы. X /\X = X X \/ X = X 1 8. Екі рет терістеу амалы. X= X 18$

6. Де Морган ережесі.

X 1 \/ X 2 \/X 3 = (X 1 /\ X 2 /\X 3

X 1 /\X 2 /\ X 3 = X 1 \/X 2 \/ X 3 )

7. Жойылу заңы.

X /\X = X

X \/ X = X 1

8. Екі рет терістеу амалы.

X= X

$9. Айнымалы мен оның керісіне орындалатын амал. Комплементарлық заң (латын тілінен аударғанда– толықтыру) X \/X = 1 X /\X = 0 10. Тұрақтылар қасиеті X \/0 = X X\/1 = X X /\1 = X X /\0 = 0 18$

9. Айнымалы мен оның керісіне орындалатын амал. Комплементарлық заң (латын тілінен аударғанда– толықтыру)

X \/X = 1

X /\X = 0

10. Тұрақтылар қасиеті

X \/0 = X X\/1 = X

X /\1 = X X /\0 = 0

Логикалық операцияларды орындау келесі кестеде көрсетілген приоритетпен(басымдылықпен) жасалады.

басымдылығы

операция

инверсия

конъюнкция

дизъюнкция

mod 2 бойынша қосу

Бір басымдылықтағы операциялар солдан оңға қарай орындалады. Операциялардың орындалу ретін өзгерту үшін жақшалар қолданылады. Жақша ішіндегі операциялар бірінші ретте орындалады

Бұл заңдар мен заңдылықтар – симметриялы, яғни олардың дизъюнкциялық және конъюнкциялық түрлері болады. Бұл заңдардың кейбірі дәстүрлі алгебрада қалыптасқан заңдар, сондықтан олардың дұрыстығы күмән тудырмайды, ал дәстүрлі алгебраға тән емес, жаңа заңдар мен заңдылықтардың дұрыстығына көз жеткізу (яғни, оларды дәлелдеу) аргументтерінің орындарына олардың сәйкесті мәндерін (0 мен 1) қойып тексеру арқылы жүзеге асырылады.