Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Questions regarding Boolean algebras as structures, or regarding functions defined from/to Boolean algebras fit into this tag very nicely. For Boolean logic use the tag propositional logic

learn more… | top users | synonyms

1
vote
2answers
35 views

prove $(p → r) ∨ ( q → r)$ logically equivalent to the statement $(p∧q) → r$

I came across this problem, it asks to use logical equivalences (see image), show that $(p → r) ∨ (q → r)$ logically equivalent to the statement $(p ∧ q) → r$ (aka definition of biconditional) After ...
0
votes
0answers
19 views

Why aren't these two expressions equivalent by use of DeMorgan's Laws?

This has thoroughly confused me. According to DeMorgan, the following expressions are equivalent. $$ '(A*B) = 'A +'B $$ However, I have come across the following expression: $$ '('A+B*C) $$ By using ...
0
votes
0answers
46 views

How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
3
votes
2answers
30 views

Functional separation of regular open sets of a topological space

Let $\langle X,\mathscr{O}\rangle$ be a topological space. We say that disjoint $A,B\in 2^X$ are functionally separated iff there exists a continuous function $f\colon X\to [0,1]$ such that: if ...
1
vote
1answer
123 views

Proof that {xor,not} is not functionally complete

I am trying to figure out the formal proof that set of {xor, not} is not a functional complete system. Firstly I tried to build it by structural induction and show that any formula created by using ...
0
votes
1answer
95 views

How to create an AND , OR , XOR and NOT gates with a fredkin gate?

Ok so I am studying for an exam which is about logic gates and circuits , etc .The problem I have is with these two questions that are in the picture , it says build an AND , OR and NOT gate using ...
0
votes
2answers
46 views

How to test CNF for satisfiability?

If we have a conjunctive linked expression where only the following clauses are allowed: $A_i, \quad \neg A_i, \quad A_i \vee \neg A_j, \quad \neg A_i \vee A_j$ Example: $A_1 \wedge (A_2 \vee \neg ...
0
votes
0answers
18 views

Number of possible unate functions possible

An unate function f is one which is constant or can be represented by an SOP using either complemented or uncomplemented literals for each variable. My question is : How many such unate functions in ...
0
votes
2answers
49 views

lambda calculus, definition of true and false

Are the following lambda-calculus definitions axiomatic? true: $\lambda xy.x$ false: $\lambda xy.y$ Is the definition truly arbitrary? In my impression, it looks like we could just swap the ...
0
votes
1answer
32 views

Correspondence between ideals and congruences of Boolean algebras

I'm trying to prove that $con(B) \simeq I(B)$ where $B$ is a Boolean algebra and $con(B)$ is the lattice of congruences on $B$ and $I(B)$ is the lattice of ideals on $B$ I found a map s.t. for a ...
0
votes
1answer
27 views

Express logic and with +,-,*

How can a logic and be expressed using only the arithmetic operators $+,-,*$ on $\{0,1\}$, taking $1 = $ True? To be precise: What function that uses only $+,-,*$ is $1$ when both arguments are $1$ ...
0
votes
0answers
18 views

Boolean Algebra: Minterm/Maxterm with Constant?

I have a rather definition related question I guess. I have several Boolean Terms given (independent from each other, without a full function) and have to decide whether they can be seen as a Minterm, ...
0
votes
1answer
33 views

Obtaining one of DeMorgan's laws from the other

How can: $\lnot(x \lor y \lor z)=\lnot x \land \lnot y \land \lnot z$ be obtained from: $\lnot (x \land y \land z) = \lnot x \lor \lnot y \lor \lnot z$    such that $x, y, z $ are ...
0
votes
0answers
35 views

What is a complete set? Why its useful?

I am learning Discreet Mathematics and while learning Boolean algebra I came across the term Complete Set, the prof says that any formula that can be written with ...
1
vote
0answers
40 views

Sum of Products Expression using $K$-map

Determine the minimum SOP, sum of products expression using $K$-Map $F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’$ My problem is, in my class room we have always done ...
0
votes
2answers
23 views

Problem simplifying equation using boolean algebra

I have this boolean equation: A'.B'.C'.D' + A'.B.C'.D' + B'.C'.D + B.C'.D Using a Karnaugh map I find I can simplify the above to: ...
0
votes
0answers
4 views

Regarding monomials of size k

I came across this example during my Math lecture: Consider a boolean space over 4 variables, $X = {x_1,x_2,x_3,x_4}$. Let I be the space of all monomials of size 3 over X. I understand that one ...
0
votes
0answers
26 views

Prime Implicants and Essential prime implicants to solve a K map

I was used to solve K maps directly by grouping 1 elements and then writing down the expression until I learnt the concept of Prime Implicants and Essential Prime Implicants. Is it necessary to use ...
0
votes
0answers
23 views

Simplifying this boolean expression

Can anyone explain how this expression can be simplified (Where + denotes Or, . denotes And and - denotes Not) from $$C \land ((\neg A \lor B) \lor (A \lor -B))$$ to $$(C \land B) \lor (C \land ...
6
votes
2answers
134 views

Can we describe multiplication on $\mathbb{F}_{2^n}$ as action on subsets of $n$-element set?

The symmetric difference between two set $A$ and $B$ denoted $A \triangle B$ is defined as the set $(A - B) \cup (B - A)$ or equivalently $(A \cup B) - (A \cap B)$. Some years ago I was quite excited ...
0
votes
1answer
24 views

How can I find POS from given SOP?

Here are the sets of POS C + B’D (AC) + (B’CD) + (AB’D) (BC) + (A’CD’) + (A’B’C’D) (BC) + (ACD’) (B’C) + (A’CD’) + (ACD) This (') stand for NOT. Please help!
0
votes
0answers
16 views

Finding Prime Implicants in a K-Map

I've been trying to solve this EE question about finding prime implicants from a K-map but there are just so many options, I really cannot be sure which ones I should pick. My K-map looks like this: ...
1
vote
2answers
40 views

Process of simplifying boolean expression

I have an expression: $$y = \overline{ab}c\overline{d} + \overline{ab}cd + \overline{a}b\overline{c}d + \overline{a}bcd + a\overline{b}cd + ab\overline{c}d$$ I've constructed the circuit for this ...
0
votes
1answer
49 views

Algebraic form from truth table with two outputs; simplifying boolean expression?

I have a truth table like below: x y z | a b ----------- 0 0 0 | 1 1 0 0 1 | 0 1 0 1 0 | 0 0 0 1 1 | 0 0 1 0 0 | 0 1 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 0 0 If the ...
0
votes
0answers
12 views

Minimizing this Boolean Algebra expression

I have the expression... AB'C'D+ABC+AB'D' I completely forget how to do this from Discrete Math, the answer I got was BC in the end but I feel this is wrong. Can someone do this one as an ...
0
votes
1answer
25 views

Why does the number of 1s in a prime implicant set in a Karnaugh Map need to be a power of 2?

Pretty much the title. We were learning about Karnaugh maps in class today and they didn't really mention why it has to be a power of 2. A quick google search basically confirmed that it needs to be a ...
-1
votes
1answer
38 views

simple logic to use only one operator to construct a function [closed]

So I was doing some of the problems on the book for discrete mathematics and I encountered this problem: We define a new operator ⊙ as follows: x ...y.... x⊙y F... F... T F... T... F T... F... F ...
2
votes
1answer
15 views

Looking for a particular algebraic mapping from one Boolean matrix to another

Consider the following Boolean matrix: \begin{align} X&=\begin{bmatrix} 1&1&1&1&1&1&1&1\\ 1&1&1&1&0&0&0&0\\ ...
0
votes
2answers
44 views

finding shortest equivalent expression

I am trying to find the shortest equivalent expression of the following: ((C → D) $\wedge$ (D → C)) $↔$ (C $\wedge$ D ∨ ¬C $\wedge$ ¬D) I have "simplified" the expression into the following: ...
1
vote
1answer
48 views

functional completeness of $\{\to\}$ [duplicate]

Given that the set {∨, $\wedge$ , ¬} is functionally complete, how would I prove whether the set $\{\to\}$ is functionally complete? expressing $→$ in terms of $∨$: $¬A∨B$ expressing $→$ in terms ...
1
vote
1answer
74 views

proof of functional completeness of logical operators

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators? a) $\{\vee,\neg\}$ b) ...
1
vote
2answers
99 views

Prove that the set {→, ¬} is functionally complete

I am not sure how to do this question. I have looked at some of the other similar questions but to no avail I know that for a set of operators to be functionally complete, the set can be used to ...
0
votes
0answers
28 views

Essential Prime Implicants confusion

I'm trying to understand what an essential prime implicant is. This picture says that there are 2 essential prime implicants but why can't we say that there's none? Can't we cover those ones ...
1
vote
0answers
40 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p ...
0
votes
0answers
48 views

Simplifying a Boolean expression for two-level NAND gate circuits

The expression is: F = (X' + Y' + Z')(Y' + A') I have no clear idea on how to go about simplifying this with Boolean algebra. After it's simplified, I'll need to implement it only using NAND gates. ...
0
votes
1answer
56 views

Minimizing using a Karnaugh map when given as subscripts F4,2655

I have to minimize the expression using minterms and a Karnaugh map: $F_{4,2655}$ How might I get this expression I am given into a form much like a typical boolean algebra minification question? I ...
0
votes
0answers
22 views

Embed boolean lattice into complete atomic boolean lattice

Trying to answer this question, I attempt to apply the solution of this question. To use this way, I may need to embed a boolean lattice into a complete atomic boolean lattice. Please help to ...
0
votes
1answer
28 views

Is canonical SOP/POS form for a boolean expression unique?

I was trying to find equivalence between two boolean expressions and thought if I convert both of them to canonical sum of product or product of sum form they should match. But I am not sure if these ...
0
votes
1answer
23 views

boolean algebra simplification solving

Can anyone help me out on this boolean algebra simplification...im not sure with my answer. X’YZ + XY’Z’ + X’Y’Z’ + XY’Z + XYZ my answer is x'yz+y'z'+xz but badly not sure of it! can you check thnks ...
0
votes
1answer
30 views

Boolean Simplification questions

I'm having some trouble getting a handle with this course. We are starting Boolean algebra and my professor wants us simplify the following: Im sorry for the ignorance but I can't find a good ...
0
votes
1answer
38 views

Boolean algebra: How does the imply operator work?

I am conflicted because our professor said that "(not) A implies B only and only if A and B = 0" which doesn't match with what I found on Wikipedia or other books on Boolean algebra: "A implies B = ...
2
votes
2answers
47 views

Name for a Boolean ring without a unit element

Is there a standard name for a Boolean ring without a unit? I read that historically ring and Boolean ring used to refer to possibly non-unital objects: The old terminology was to use "Boolean ...
0
votes
1answer
21 views

Simplify Boolean Expression

so I have this expression and I have to simplify it to minimum SoPs $(x+(y'(z+w)')')'$ so my final answer is $x'y'z'w'$ but I think there is something wrong or trick can some one help me or tell ...
-1
votes
1answer
28 views

Is D646 a Boolean Algebra?

I read here: http://mathoverflow.net/questions/193924/how-to-recognize-if-a-lattice-is-distributive?newreg=1439abdc43e24ebcb32afa0532b74ecb that N5 and M3 lattices are not distributive. So I concluded ...
0
votes
2answers
29 views

How are these two boolean expressions same?

How does AB(1+C'D) simplify into AB in boolean algebra? I cannot compare their truth tables since literal number of these two ...
0
votes
1answer
128 views

Duality Principle vs. DeMorgan Law

What is the difference between the two? Duality Principle states that any theorem in switching algebra remains true if 0 and 1 are swapped and + and . are swapped throughout. DeMorgan's Law says ...
0
votes
2answers
92 views

Finding minterms from a boolean expression

I have a question regarding the process of finding minterms. Problem: Find the minterms of the following expression by first plotting each expression on a K-map: ...
0
votes
0answers
23 views

Construct a set of 4 elements and an operation * that is closed, with universal identity, no universal inverse. Can it be commutative?

I am very confused on this problem I have for math. Constructing my own table for this as well as determining identities and inverses leaves me clueless. Any help would be greatly appreciated!
0
votes
1answer
26 views

Simplify Boolean Expession

Can anyone verify this. If I can wrong can you point me in the correction direction: $$AB'C'+A'B'C+A'BC'+AB'C = B'(AC'+A'C+AC)+A'BC' \rightarrow B'(AC'+C)+A'BC' \rightarrow B'(C+A)+A'BC'\rightarrow ...
1
vote
1answer
46 views

Poset is complete iff it is cocomplete

In Awodey's Category Theory, page 130, he says: A poset is (co)-complete if it is so as a category, thus if it has all set-indexed meets (resp. joins). For posets, completeness and cocompleteness ...