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
3
votes
5
answers
11k
views
Algebraic proof of De Morgan's Theorems
Could someone give me an algebraic proof of De Morgan's Theorems?
I already know the graphic proof with the truth table, but I need to understand the algebraic way.
EDIT
I try to explain better. ...
- 483
3
votes
4
answers
838
views
How is material implication the same as subset?
I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then ...
- 1,324
3
votes
5
answers
425
views
The logic involved in contradiction via the irrationality of $\sqrt{2}$ as an example
I first want to issue my own interpretation of the proof that $\sqrt{2}$ is irrational.
First, for the sake of contradiction, let's assume it is in fact rational. This means we can write $\sqrt{2} = ...
- 5,651
3
votes
2
answers
74
views
Reducing Boolean expression to an equivalent form
Consider two points from an arbitrary subset of $\mathfrak{R}^n$, namely, points $$p_1 = (x_{11}, x_{12}, \dots, x_{1n})$$ and $$p_2 =(x_{21}, x_{22}, \dots, x_{2n})$$
Let $P_1$ denote the ...
- 85
3
votes
1
answer
139
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?
- 133
3
votes
3
answers
2k
views
Logic Knights and Knaves problem involving implication question
I'm kinda stuck on the following puzzle problem, and I will appreciate it if anyone can help point out any logic errors.
Question:
John and Sarah are members of the island of knights and knaves, ...
3
votes
2
answers
211
views
Propositional logic: Proof question (p∧q)→r⊢(p→q)→r
Am I correct to assume that there is no proof for $$(p∧q)→r ⊢ (p→q)→r$$
I´ve spent hours trying to figure it out, by now I suspect there might have been a mistake in the exercise. I have been able to ...
- 33
3
votes
1
answer
78
views
Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)
I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some ...
3
votes
1
answer
470
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'$$
- 273
3
votes
1
answer
90
views
proof that any boolean function can be written in canonical form
It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is ...
- 35
3
votes
2
answers
109
views
Simplifying the boolean expression $AB+BC'D'+AC+AD$
I'd like to simplify the expression
$$AB+BC'D'+AC+AD$$
Logically, I understand why the AB term isn't needed, if both A and B are true, then at least one of the other terms will always be true, making ...
- 33
3
votes
1
answer
126
views
Are parentheses/connectives always necessary in representing expressions built with a single sole sufficient operator?
The Wikipedia page on the Sheffer stroke provides two ways of simplifying expressions consisting only of the Sheffer stroke:
Removing all occurrences of the logical connective '$\mid$' in the ...
- 727
3
votes
2
answers
1k
views
Tautology, Valid, Contingent, Unsatisfiable, Contradiction: relationship?
I am trying to clear my doubts about various terms: tautology, contradiction, contingent, satisifiable, unsatisfiable, valid and invalid. I have read on them from various sources and was thinking ...
- 1,317
3
votes
2
answers
390
views
Proving a boolean algebra relation
I just started reading the book Probability Theory the Logic of Science by Jaynes and on pg. 13 he includes this exercise, which I'm having trouble proving:
$C\equiv(A+\bar B)(\bar A+A \bar B)+\bar ...
- 690
3
votes
1
answer
2k
views
Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)
I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$.
For example: ...
- 2,517
3
votes
2
answers
114
views
Proof by induction of inadequacy of a propositional connective
I have the following truth table of a newly defined logical operator and have to prove its functional incompleteness via structural induction.
My idea is that that you cannot express the always true ...
- 51
3
votes
2
answers
1k
views
Simplify $(P \wedge Q \wedge R)\vee(\neg P\wedge Q\wedge\neg R)\vee(\neg P\wedge\neg Q\wedge R)\vee(\neg P \wedge\neg Q\wedge\neg R)$
Let $\psi_{1} := (P \wedge Q \wedge R)\vee(\neg P\wedge Q\wedge\neg R)\vee(\neg P\wedge\neg Q\wedge R)\vee(\neg P \wedge\neg Q\wedge\neg R)$ and
Let $\psi_{2} := (\neg P \wedge \neg Q) \vee (\neg P \...
3
votes
1
answer
117
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 q)\...
- 75
3
votes
0
answers
103
views
Do the integers 1 and 0 mean different things in Boole's original logic and modern Boolean algebra?
I understand that the modern notion of Boolean algebra was adapted by Peirce, Schroder and others from Boole's logic of classes. Boole spoke of 1 and 0 as representing the Universe of Discourse and ...
- 79
2
votes
2
answers
227
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 ...
- 317