Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.
3
votes
2answers
234 views
Prove: $ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $
How could I derive the following proposition:
$$ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $$
using any of the following axioms:
1) $A→(B→A)$
2) $(A→(B→C))→((A→B)→(A→C))$
3) ...
1
vote
1answer
76 views
Generalized “Duality” of Classical Propositional Logical Operations
Duality in propositional logic between conjunction and disjunction, $K$ and $A$ means that for any "identity", such as $KpNp = 0$ (ignoring the detail of how to define this notion in propositional ...
2
votes
2answers
669 views
Is there a systematic way to write an expression in disjunctive normal form?
Here is disjunctive normal form.
http://en.wikipedia.org/wiki/Disjunctive_normal_form
I understand what it is. However, I lack a systematic way of converting any complicated expression into it.
For ...
2
votes
2answers
223 views
What does this question mean?
I am looking for some to explain what does this question want from me to do?
Determine all true value assignments, if any, for primitive statements
$p, q, r, s, t$ that make each of the following ...
1
vote
2answers
141 views
Proving a simple assertion in Propositional Logic
I have to prove some Propositional Logic assertions.
Given this one: $\alpha \models \beta \Leftrightarrow (\alpha \Rightarrow \beta)$ is valid
Where $\models$ is entailment
The answer is: $\alpha ...
4
votes
2answers
307 views
How to write $X \iff Y$ in CNF form?
I know that $X \iff Y$ is true when
$X$ is True and $Y$ is True
$X$ is False and $Y$ is False
I know that there is a simple algorithm to convert to CNF form, but I don't remember it...
0
votes
3answers
389 views
Express the propositional form ie. using only the NAND operator.
Recall that the NAND operator(denoted by "|") is equivalent to AND followed by negation; that is, for any two propositions a and b, the propositional form (a|b) is logically equivalent to ￢(a∧b). ...
1
vote
1answer
220 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
1answer
108 views
Opposite of a logical expression
What is the opposite of this expression?
$p \land ( q \lor r )$
Please suggest any theorem as a starting point.
2
votes
1answer
322 views
In Satisfiability, what is the difference between the empty clause and the empty set?
The empty clause is a clause containing no literals and by definition is false.
c = {} = F
What then is the empty set, and why does it evaluate to true?
Thanks!
0
votes
3answers
3k 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
295 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’ + ...
1
vote
3answers
369 views
inference rules application (introduction / elimination): two examples
Got stuck while trying out how to apply inference rules (introduction and elimination) for the following examples:
From $\lnot(P\land Q)$ and $P$ infer $\lnot Q$
From $P\lor Q$ and $Q$ infer $\lnot ...
3
votes
3answers
266 views
Adequacy theorem for propositional calculus
I have been thinkig about the following classical theorem of propositional calculus:
Adequacy Theorem:
if $A$ is a tautology then $A$ is provable by the logical axioms
Now "$A$ is a tautology" ...
2
votes
1answer
355 views
Relation between XOR and Symmetric difference
I noticed that XOR and symmetric difference use the same symbol, $\oplus$.
They also seem to have a similar structure:
XOR: $(\neg P\wedge Q)\vee(P\wedge \neg Q)$
Symmetric Difference: $(A\cap ...
2
votes
2answers
256 views
Propositional Logic Proof of $\vdash \lnot (p \supset q) \supset (p \land \lnot q)$
$\vdash \lnot (p \supset q) \supset (p \land \lnot q)$
I need to prove the above proposition via intuitionistic logic rules and/or natural logic rules. I guess it is not possible to prove with ...
1
vote
2answers
79 views
Sums of truth-table values mod 2 range over all truth tables
Let $A=\lbrace0,1\rbrace$. There are 16 distinct functions $f_i:A^2\to A$.
Choose a permutation $P=\left(a_1,\ldots,a_4\right)$ of the elements of $A^2$, and for each $i$ consider the ordered ...
10
votes
4answers
372 views
If both $P$ and $Q$ are true , how can I tell that $P$ implies $Q$?
I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon.
I have a big problem understanding Implication. I ...
4
votes
3answers
254 views
How complicated is the set of tautologies?
Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.
How ...
4
votes
2answers
284 views
How Many Theorems (Tautologies) Exist of 5, 6, 7, 8, and 9 Letters?
Suppose we only have the material conditional C and logical negation N for a system of propositional calculus, with only variables and no constants in any formula. Suppose that formulas like Cpq ...
4
votes
5answers
272 views
Logical NOT of an implication
I was looking through my notes but I was unable to find the answer to this, which I need to start am assignment question.
What would the following be, in terms on moving the negation inside the ...
2
votes
2answers
140 views
Algebraic Solution to Prove Tautology
I need an algebraic solution to show this is a tautology:
$\displaystyle [(p\lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$.
Thanks
2
votes
2answers
139 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 ...
1
vote
1answer
185 views
Proving a theorem in classical propositional logic
In van Fraasen and Beall's book Possibilities and Paradox, there is the following line (on pg 7):
"In classical propositional logic we can prove that $$(A \iff B) \lor (A
\iff C) \lor (B \iff ...
3
votes
1answer
910 views
Problem in understanding p implies q
I am trying to understand what “$p$ implies $q$” means. I read that $p$ is a sufficient condition for $q$, and $q$ is a necessary condition for $p$.
Further from Wikipedia,
A ...
2
votes
3answers
200 views
Logical propositions, which one is true and how to write a short proof?
I am studying for an entrance exam. Now I am stuck on this question:
Suppose that P, Q are propositions such that "P or Q" is true. For
each proposition (1), (2) and (3) which of the following ...
1
vote
2answers
207 views
Why is $p\Rightarrow q$ equivalent to $\neg p\lor q$ and how to prove it
I don't know how to prove that $p\Rightarrow q$ is equivalent to $\neg p\lor q$ ,here is the link p=>q . And I don't know how wolframalpha generate "Minimal forms" .
Can you prove $p\Rightarrow q ...
0
votes
2answers
124 views
Confirm some logical inferences for me please?
Sorry, I am just preparing some notes for my students and want to double check I have my facts right before I give the notes to them.
So these are my premises:
$\lnot p\rightarrow o$
$s\rightarrow ...
3
votes
1answer
144 views
Question about maximal consistency
Let $\sigma$ be a consistent set of propositions such that for every set $\gamma$, either $\sigma$ is proofwise stronger than $\gamma$ that is {$\alpha : \sigma \vdash \alpha$} $\supseteq$ {$\alpha ...
1
vote
1answer
181 views
For any $\alpha$, does a set $\gamma$ always exist so $\gamma\vdash\alpha$ or $\gamma\vdash\lnot\alpha$?
In propositional Calculus, for any proposition $\alpha$ does there always exist a set of propositions $\gamma$ such that $\gamma$ $\vdash$ $\alpha$ or $\gamma$ $\vdash$ $\neg\alpha$?
1
vote
2answers
109 views
Cofusing partial order “implies”, on logic and that on sets
I feel confused comparing partial order on sets and that on logic.
$$x\ge 1 \implies x\ge 0$$
Here we see a smaller set "implies" a bigger set
But, if we know three facts, fact1,fact2,fact3, we ...
1
vote
1answer
119 views
Appropriate book for propositional logic
I am not looking for a good book but an appropriate book that is suitable for my logic course. Currently the professor only offers lectures. (Not sure why, perhaps there is no universal approach to ...
3
votes
3answers
193 views
Distinguishing between valid and fallacious arguments (propositional calculus)
I am having some difficulties understanding logical arguments. I was taught that the notion of a valid argument is formalized as follows:
"An argument $P_1, P_2,\cdots , P_n ⊢ Q $ is said to be ...
23
votes
16answers
2k views
In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?
I am studying entailment in classical first-order logic.
The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is:
...
6
votes
4answers
616 views
Help to understand material implication
This question comes from from my algebra paper:
$(p \rightarrow q)$ is logically equivalent to ... (then four options are given).
The module states that the correct option is $(\sim p \lor q)$. ...
0
votes
4answers
80 views
Showing a propositional formula is a contradiction
Please help me with showing that the expression $P\land (Q\lor \neg P) \land \neg Q$ is a contradiction? Your help is greatly appreciated
What I have tried so far:
$$\begin{align*}
&C = ...
1
vote
1answer
94 views
Simplifying a propositional formula
I have the following logical expression to solve/Simplify. Anyone able to help please??
$(P\land Q\land R)\lor (P\land\lnot Q\land R)\lor (P\land \lnot Q\land \lnot R)$
4
votes
2answers
289 views
Disjunction in Intuitionistic Logic, what about $((P \to U \lor V) \to Z)$
I wonder whether the following holds in intuitionistic logic:
$$((P \to U \lor V) \to Z) \leftrightarrow ((P \to U) \to Z) \land ((P \to V) \to Z)$$
For disjunction I assume the following two rules:
...
3
votes
1answer
1k views
Translating “neither…nor” into a mathematical logical expression
Having some difficulty doing translations for complicated neither...nor sentences.
With these characters:
~: Negation; $\vee$: Disjunction; &: Conjunction.
I'm trying to translate and ...
5
votes
1answer
236 views
What is the reverse distributive technique?
I have a solution to a logic problem involving propositions that I don't undersand how a particular step was carried out.The professor called the step I'm having trouble with reverse distribution.
...
3
votes
0answers
276 views
Constructor And\Or-graph on function transition of the alternating automata
In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
3
votes
3answers
90 views
Are standalone propositions affected by negation operators?
In propositional logic, for example:
$$\neg p \vee q.$$
If $p$ is true at the outset, does that mean it must be considered false when comparing with q in the disjunction?
P.S. I am unsure about ...
5
votes
5answers
2k views
Associativity of logical connectives
According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator?
The implies ...
1
vote
1answer
158 views
Negating a statement
State in words the negation of the following sentence: For every martian M, if M is green, then M is tall and ticklish.
I got the right answer to this, give or take a few words, but this is a ...
3
votes
2answers
875 views
Proof of logical equivalence
I have the standard logical equivalence:
$(p\rightarrow q)\wedge(q\rightarrow r)\Leftrightarrow p\rightarrow (q\wedge r)$.
Using several distributive laws I was able to get it down to:
$(\neg ...
2
votes
3answers
322 views
Understanding this proof by contradiction
Let $c$ be a positive integer that is not prime. Show that there is some positive integer $b$ such that $b \mid c$ and $b \leq \sqrt{c}$.
I know this can be proved by contradiction, but I'm not ...
