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
129k
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
307
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
976
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
254
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 ...
- 668