All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
30
votes
5
answers
99k
views
Prove XOR is commutative and associative?
Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative
and associative.
I know I can show using a truth table.
But using boolean algebra?
How do I show? I totally have no ...
- 501
23
votes
3
answers
130k
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:
...
- 3,470
18
votes
4
answers
125k
views
Find DNF and CNF of an expression
I want to find the DNF and CNF of the following expression
$$ x \oplus y \oplus z $$
I tried by using
$$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$
but it got all messy.
I also ...
- 1,002
11
votes
6
answers
18k
views
Example of use De Morgan Law and the plain English behind it.
I am currently reading "Discrete Mathematics and Its Applications, 7th ed", p.29.
Example:
Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer”.
...
- 368
11
votes
1
answer
5k
views
What is the difference between Boolean logic and propositional logic?
As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something?
I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
- 107
9
votes
2
answers
308
views
Is 1+1=2 logically equivalent to 99+1=100?
I am trying to understand logical equivalence.
From what I understand, two formulae are logically equivalent if they have the same truth values under all interpretations. So,
$$x+1=y\dashv\vdash x+(2-...
8
votes
4
answers
6k
views
Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?
Below, an attempt at solving a knight/knave puzzle using the truth table method.
Are there other methods?
Source : https://en.wikipedia.org/wiki/Knights_and_Knaves
user654868
8
votes
4
answers
561
views
Why does $AB + BC + CA = (A\oplus B)C + AB$ not imply $BC + CA = (A\oplus B)C$ in boolean algebra?
I am new to Logical Inequalities. Please bear with me if I am inexplicably stupid.
The following is a Proven Equality:
$$AB + BC + CA = (A\oplus B)C + AB$$
I noticed that I cannot "cancel out" $AB$ ...
- 101
8
votes
2
answers
1k
views
How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?
For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - $...
- 139
7
votes
4
answers
4k
views
proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$
I am currently working through Velleman's book How To Prove It and was asked to prove the following
$(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$
This is my work thus far
$...
7
votes
2
answers
977
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 ...
- 71
7
votes
5
answers
6k
views
Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.
I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$".
Regarding this ...
- 645
7
votes
2
answers
255
views
Why is $((p \land q) \Rightarrow z) \Rightarrow (p \Rightarrow z) \lor (q \Rightarrow z)$ true?
I will propose a counterexample to $$((p \land q) \Rightarrow z) \Rightarrow ((p \Rightarrow z) \lor (q \Rightarrow z)).$$ Let's assume that $p$ is "$n$ is divisible by $2$", $q$ is "$n$...
7
votes
2
answers
159
views
Why is this part of the composed proposition false?
Currently I'm studying logic, but I do not understand a certain step. It is the step from row $2$ to $3$. I see that $-q$ is the common factor on both sides of the middle or operator, but I did not ...
- 704
7
votes
3
answers
296
views
Is $P(tautology) = 1$? What are the connections between logic and probability?
It's well-known that sets are "isomorphic" to logic: if we treat $\varphi(A_1, A_2)$ as a shorthand for $\forall x: \varphi(x \in A_1, x \in A_2)$ then $A \land B \equiv A \cap B$ and $A \rightarrow B ...
- 678
6
votes
1
answer
193
views
Given the $P⇒Q$ and $¬P$, prove that we cannot deduce $¬Q.$
Given the known theorems $P \Rightarrow Q$ and $\lnot P$, prove that we cannot deduce $\lnot Q.$
I made the truth table for $P \Rightarrow Q:$
Now, if $P \Rightarrow Q$ is a theorem, that means that ...
- 224
6
votes
1
answer
346
views
Construct an OR gate when missing input information
Is there a way to construct an OR gate when the input for one combination is unknown?
For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = T$:...
- 391
5
votes
3
answers
431
views
Proving the equivalence without making use of Truth Tables
How would I prove this without using the truth table? If anyone can help me with this it would be greatly appreciated
$$(¬A \lor B) \lor (¬B \lor ¬A) ≡ ¬A$$
This is what I got so far and I'm stuck ...
- 91
4
votes
3
answers
36k
views
How to prove that $[(p \to q) \land (q \to r)] \to (p \to r)$ is a tautology without using the truth table?
I am looking for a way to prove that the statement, $[(p \to q) \land (q \to r)] \to (p \to r)$, is a tautology without the help of the truth table. By using only Laws and Theorems like De Morgan's ...
4
votes
5
answers
430
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?
- 181
4
votes
2
answers
11k
views
is bitwise xor completely associative?
The bitwise xor (exclusive or) operator has the following truth table:
$$
\begin{array}{c|cc}
\text{^}&0&1\\
\hline
0&0&1\\
1&1&0
\end{array}
$$
It is true that if $a,b,c,d$ ...
- 21.9k
4
votes
1
answer
2k
views
Finding the atoms and elements of a Lindenbaum–Tarski algebra
Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$
(1) Find all the atoms of $B$.
(2) How many elements of does $B$ have?
So I think I know what an atom is, but I'm still not sure ...
- 575
4
votes
1
answer
2k
views
Proof of Principle of Duality: Show that $φ$' is logically equivalent to $¬φ$
Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.
Let $φ$ be a formula built up using ...
- 1,458
4
votes
3
answers
265
views
Why do I keep running into contradictions in this problem (Knights and Knaves variation)?
Edit: I've attempted to solve this another way and posted it as a possible answer. Hesitant to accept it, and would appreciate if anyone could go over it and confirm it's the way to go.
There is an ...
- 329
4
votes
2
answers
277
views
How math deals with state or "algebra of sequential logic"
Boolean algebra is well-studied and you could easily find a lot of introductory materials on different operators, properties, how eveything is nicely related to the algebra of sets, and so on.
Coming ...
- 167
4
votes
1
answer
5k
views
Tseytin transformation example
I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet.
I pretty much understand the steps until I get to the point I have to convert all ...
- 43
4
votes
1
answer
496
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 $A⊆(...
- 68.1k
4
votes
1
answer
4k
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, the ...
- 41
4
votes
1
answer
293
views
Proving ◦ is either nand or nor if ◦ is a binary operator that can define negation and all other binary operators by itself.
I have a outline of the proof in my book but I am not able to understand the second part of it.
Suppose that $\circ$ is a binary operator that can define all the other operators. Negation
must be ...
- 426
4
votes
3
answers
1k
views
Relation between propositional logic, boolean algebras and truth tables
I am a bit confused with the relation between propositional logic, boolean algebras and truth tables.
Propositional logic starts with a language over a set of primitive propositions, they are called ...
- 41