2
votes
3answers
61 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
3
votes
1answer
73 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
1
vote
5answers
69 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
1answer
66 views

Truth table to prove statements

A, B and C. When questioned A says ''If B did not do it, then it was C." B says ''A and C did it together or C did it alone". C says ''We all did it together." How would i be able to put these into ...
0
votes
1answer
31 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
0
votes
0answers
62 views

How to write Propositional logic equation

Given $n-1$ teams and $m-1$ days, provide a propositional logic equation to illustrate the following: each team can only play 1 home game per day. All possible permutations must be played. I'm not ...
0
votes
1answer
49 views

How to give an assignment of boolean values such that this expression is evaluated to true?

Given the expression $E$, is there an assignment of boolean values ($true$ or $false$) that we can give to our variables such that this is evaluated to $true$? $E = (¬x + z + ¬v) · (¬v + w) ·(¬z + ...
1
vote
3answers
116 views

Correct progression from DNF to CNF?

Trying to figure out how to transform this predicate from disjunctive normal form to conjunctive normal form (repost of an earlier question): $$( P \land Q ) \lor ( R \land S ) \lor ( P \land S )$$ ...
3
votes
4answers
157 views

How is $((X\to Y)\to X)\to X$ a tautology?

$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ converted to its disjunctive normal form is $X' + X$. Why/how does this show me why this formula a tautology?
0
votes
2answers
37 views

Simplification of boolean algebra from “not s and p” to “not s”

I am trying to learn more about "Rules of Inference" and their application, but one thing always confuses me, and that is simplification "not s and p" to "not s". I have looked at some examples: ...
0
votes
2answers
31 views

Discrete: Boolean Function

~(pV~q) v (~p^~q) is equal to ~p? I know the answer is yes and I've been using DeMorgans initially then distributive law after. However I keep messing up on the algebra. Help is appreciated so I can ...
-1
votes
1answer
89 views

boolean expression help simplify

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
1
vote
1answer
185 views

Check if tautology (w/o truth table)

$(A+B)(A+C)(B+C) = AB + AC + BC$ is a tautology (checked with Wolfram Alpha) and not hard to see if you apply duality principle $(invert + * 0 1)$ But how to prove with simplyfication It'S not much ...
2
votes
2answers
57 views

Ist it a tautology w/o truth table

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right. That'S what I have: AB + CD = A(C+D)B(C+D) AB + CD = ...
0
votes
1answer
105 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
1
vote
1answer
56 views

Where can I learn more about these two functions obtained from IFF and XOR?

Given a set $X$, write $\mathrm{heaps}(X)$ for the set of all finite heaps (or 'multisets', if you prefer) on $X$. Under this definition, it is well-known that if a binary operation $*$ on a set $X$ ...
4
votes
1answer
75 views

Can we convert this statement about sets into a statement of propositional logic?

A question was just asked here about proving $$A⊆(B∪C)⟺A\setminus C⊆B.$$ We can prove this statement directly, using the concepts of first-order logic. "Suppose $x \in A \setminus C$ and that ...
5
votes
2answers
168 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
3
votes
1answer
84 views

Boolean Algebra Transform

I am revisiting Boolean algebra after a long while. Can somebody help show me how to simplify the LHS to get the RHS? $$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
2
votes
2answers
128 views

How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes $$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align} $$ However, I can't work out how to prove that it becomes that ...
4
votes
3answers
7k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
2
votes
2answers
2k views

Simplifying the following expression using Boolean Algebra

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR a'.b'.c' + a.b'.c' + a.b.c' This is what I have so far. a'.b'.c' + ...
0
votes
2answers
256 views

Boolean Algebra equivalency

Which Boolean algebra laws are required to show that $$(\lnot y \land \lnot z) \lor (x \land ((\lnot y \land z) \lor (y \land \lnot z))) = (\lnot y \land \lnot z) \lor (x\land (\lnot (y \land ...
2
votes
4answers
111 views

Proof that $B \land ( B \lor C) = B$?

In my logic design exam today I was given this question: Show that: $$ B \land ( B \lor C) = B $$ It's asking for a proof for this expression. Could someone please explain how such expression ...
1
vote
0answers
204 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
1
vote
1answer
166 views

Transforming statements of a query language to propositional logic

I have a custom query language which expresses containment relations between variables. Containment in this context is simply an object (A) in programming language X (java/C#/python etc: a language ...
1
vote
2answers
504 views

Boolean Simplification: (A+C)(!A+B)(B+C) = BC

How might I solve this? I can't find any problem similar to this, and I always end up with the wrong terms. If (AB) = 0 and (A+B) = 1, prove that (A+C)(!A+B)(B+C) = BC
-1
votes
2answers
459 views

Boolean Algebra - Truth Table

X'Y'Z' + XYZ I have the equation above (Boolean Algebra truth table), and as I know, if I get x' and the value of x is 0, the value will change to 1. But Y' with the top bar being higher, what ...
0
votes
1answer
119 views

Converting a Proposition to DNF using proof systems

I have been attempting to convent a prop to DNF using a group of common rules, i have applied them all but i think i should be able to get it smaller, This is what I've got so far. Thanks! $$(p \wedge ...
2
votes
1answer
284 views

Lindenbaum Algebras

After reading this page, I still have some questions about Lindenbaum algebras. Assume that the scope is a propositional language with a denumerable set X of propositonal variables. In that case, ...
3
votes
1answer
74 views

Chains in the Lindenbaum algebra

What is the easiest example of an infinite chain in a Lindenbaum algebra for the propositional calculus? Does there exist an infinite antichain in a Lindenbaum algebra?
1
vote
1answer
421 views

Expanding this boolean expression

Can this Boolean expression: $$A*\overline{A*B}$$ be expanded to give: $$A*\overline{A} * A*\overline{B}$$ Although that appears to reduce to zero? I know $A(\overline{A+B})$ can be expanded to ...
0
votes
3answers
4k views

De Morgan's Theorems

Could someone give me an algebraical demonstration of the De Morgan's Theorems? I already know the graphic demonstration with the truth table, but I need to understand the algebraical way. EDIT I ...
0
votes
1answer
366 views

Simplify boolean expression

$(xy’+z)’\cdot((xz)’+y')$ $$\begin{align*} (xy’+z)’\cdot ((xz)’+y’) &=(x'+yz’)\cdot (x’+z’+y’)\\ &=x’x’ + x’z’ + x’y’ + yz’x’ + yz’z’ + yz’y’\\ &=x’ + x’z’ + x’y’ + yz’x’ + ...
2
votes
2answers
176 views

Can $A+\bar{A}\bar{B}+BC$ get any simpler?

I've simplified this Boolean formula quite a bit. Can it get any simpler? My definition of simple in this case is using the least amount of operators (and, or) Title is "A or (negative A and negative ...