Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикада Буль сақинасы R – R-дегі барлық x үшін 1=x²=x болатын сақина, яғни тек өзіне тең элементтерден тұратын сақина. Мысал ретінде 2 модуль бойынша бүтін сандар сақинасын келтіруге болады. Кез келген Буль сақинасы Буль алгебрасын тудырады, онда сақинадағы көбейту конъюнкцияға немесе кездесуге (∧) сәйкес келеді, ал сақинадағы қосу – эксклюзивті дизъюнкцияға немесе симметриялық айырмашылыққа (дизъюнкцияға емес ∨, ол жартылай сақинаны құрар еді). Керісінше, кез келген Буль алгебрасы Буль сақинасын тудырады. Буль сақиналары Буль алгебрасын жасаған Джордж Бульдің құрметіне аталған.
In mathematics, a Boolean ring R is a ring for which 1=x^(2) = x for all x in R, that is, a ring that consists of only idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean algebra, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨, which would constitute a semiring). Conversely, every Boolean algebra gives rise to a Boolean ring. Boolean rings are named after the founder of Boolean algebra, George Boole.
Мысалдар
Буль сақинасының бір мысалы – кез келген Х жиынының қуат жиыны, онда сақинадағы қосу симметриялық айырмашылық, ал көбейту – қиылысу болып табылады. Тағы бір мысал ретінде, Х жиынының барлық шекті немесе кошекті жиынтықтарын да қарастыруға болады, қайтадан симметриялық айырмашылық пен қиылысу операциялары ретінде. Жалпы алғанда, осы операциялармен кез келген жиындар жиыны Буль сақинасы болып табылады. Стоунның өкілдік теоремасы бойынша, әрбір Буль сақинасы жиындар жиынына изоморфты (осы операциялармен сақина ретінде қарастырылады).
One example of a Boolean ring is the power set of any set X, where the addition in the ring is symmetric difference, and the multiplication is intersection. As another example, we can also consider the set of all finite or cofinite subsets of X, again with symmetric difference and intersection as operations. More generally with these operations any field of sets is a Boolean ring. By Stone's representation theorem every Boolean ring is isomorphic to a field of sets (treated as a ring with these operations).
Біріктіру
Буль сақиналарындағы біріктіру шешіледі, яғни Буль сақиналарындағы кез келген теңдеуді шешуге арналған алгоритмдер бар. Шекті түрде жасалған еркін Буль сақиналарында біріктіру де, сәйкестендіру де NP-толық, ал шекті түрде берілген Буль сақиналарында екеуі де NP-қиын. (Шындығында, Буль сақинасындағы кез келген біріктіру мәселесі 1=f(X) = g(X) сәйкестендіру мәселесі 1=f(X) + g(X) = 0 түрінде қайта жазылуы мүмкін, сондықтан бұл мәселелер эквивалентті.) Буль сақиналарындағы біріктіру, егер барлық түсіндірілмеген функция белгілері нөлдік болса және шекті болмаса, біртұтас болып табылады (яғни, Буль сақиналарының қолтаңбасында кездеспейтін функция белгілерінің барлығы тұрақты болса, ең жалпы біріктіруші болады, әйтпесе біріктірушілердің ең кішкентай толық жиыны шекті болады).
Unification in Boolean rings is decidable, that is, algorithms exist to solve arbitrary equations over Boolean rings. Both unification and matching in finitely generated free Boolean rings are NP complete, and both are NP hard in finitely presented Boolean rings. (In fact, as any unification problem 1=f(X) = g(X) in a Boolean ring can be rewritten as the matching problem 1=f(X) + g(X) = 0, the problems are equivalent.) Unification in Boolean rings is unitary if all the uninterpreted function symbols are nullary and finitary otherwise (i. e. if the function symbols not occurring in the signature of Boolean rings are all constants then there exists a most general unifier, and otherwise the minimal complete set of unifiers is finite).