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.

learn more… | top users | synonyms (1)

2
votes
0answers
57 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
4
votes
3answers
145 views

Natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

My teacher has assigned us this exercise as part of our homework: Give a natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$ Here is an example of natural ...
1
vote
2answers
86 views

Difference between $\models$ and $\Rightarrow$

What is the difference between $\models$ and $\Rightarrow$ in propositional logic?
1
vote
1answer
24 views

Validate or invalidate the propositional argument

Validate or invalidate the following arguments $ p\to t$ $ p \to \lnot r$ $q \to p$ $\lnot t \lor r$ $r \to t$ $\therefore \lnot p \land \lnot q \land (r \iff t) $ I could only see why it is ...
5
votes
1answer
71 views

showing $\neg\alpha\vee\delta,\neg\beta\vee\neg\delta\vdash \neg(\alpha\vee\beta)\vee\delta$ is valid

Given tertium non datur ($\neg\alpha\vee\alpha$) and: \begin{align} \beta&\vdash\alpha\vee\beta\tag{1}\\ \alpha\vee\alpha&\vdash\alpha\tag{2}\\ ...
0
votes
1answer
42 views

Prove or disapprove a propositions

Let p,q and r be three propositions. Prove or disapprove $(p\to q) \land (q \iff r) \land (p \lor \lnot (\lnot q \lor \lnot r) \equiv p \land q \land r$ so, the way i do is LHS = $(\lnot p\lor q) ...
2
votes
2answers
38 views

Set logic to propositional logic

How would you convert set logic to propositional logic? In particular, I'm not sure how to handle converting $\subseteq$ For example: $$A-(\bar{B} \cup \bar{C}) \subseteq B \cap C$$ My attempt at ...
1
vote
1answer
202 views

Tracing a most-general unifier algorithm

I'm trying to trace the algorithm for getting the most general unifier, and I'm a bit confused. Can there be more than one solution? (although the adjective 'most' suggests otherwise) found online: ...
3
votes
1answer
64 views

DPLL Algorithm $ \rightarrow $ Resolution proof $ \rightarrow $ Craig Interpolation

I really need help here for an exam that I got tomorrow .. Let's say I got a bunch of constraints: $ c1 = { \lnot a \lor \lnot b } \\ c2 = { a \lor c } \\ c3 = { b \lor \lnot c } \\ c4 = { \lnot b ...
3
votes
2answers
57 views

Is entailment biconditional or conditional?

When we say a KB entails Q it means that it is never the case that KB is true and Q is false. Does this mean entailment is similar to the conditional statement KB -> Q? I'm confused because our ...
0
votes
0answers
21 views

If reduct of a formula is Tautology, Then there exists no stable models?

The Definition of a Stable model says that if I is a Stable model of F, this should be the only Interpretation that satisfies the Reduct of the Formula F. But for any formula F', If the reduct of F' ...
0
votes
1answer
35 views

Complete recursively Set

The set $\Sigma=\{ p_1\rightarrow p_2, p_2\rightarrow p_3, ... \}$ Is it complete? why? Is it recursively axiomatizable? Why? Is the consequences of this set recursive? Why? Thanks so much.
1
vote
2answers
38 views

I have confusion while translating propostions to logical expressions

I have following propositions: p:Grizzly bears have been seen in the area. q:Hiking is safe on the trail. ...
2
votes
1answer
197 views

Tautological and logical consequence

In Enderton's book on Logic, it is mentioned that Pc is not a tautological consequence of AxPx (when both are taken as sentence variables for propositional calculus) but Pc is a logical consequence of ...
0
votes
2answers
64 views

What is a Sub Formula and What is a Maximal Sub Formula in Propositional Logic

What is a Sub formula of a Propositional Formula? Suppose I have a formula C or -C Then what are the sub formulas of this and what is the maximal sub formula of this Propositional Formula. I am a bit ...
3
votes
1answer
136 views

Axioms based on $\leftrightarrow, \lor, \bot$ for propositional intuitionistic logic?

Propositional intuitionistic logic can be axiomatized based on $\;\to, \land, \lor, \bot\;$, with modus ponens $$ \text{from }\; \phi \;\text{ and }\; \phi \to \psi \;\text{ infer }\; \psi $$ as the ...
2
votes
1answer
97 views

tautologies and contradictions with $r$

I'm really struggling to understand tautologies and contradictions. I've been able to do $(p \rightarrow q) \leftrightarrow (\lnot q \rightarrow \lnot p)$ and I understand why it is a tautology, ...
3
votes
9answers
1k views

How do I prove this statement is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$ I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left ...
0
votes
1answer
100 views

Propositional Logic questions about tableau method

Hello i am learning for my exam from logic, I came across the question which i don't know how to solve it. Can tableau for a propositional formula containing an infinite path exist? Can be tableau ...
3
votes
2answers
51 views

Test the validity of the arguments

1) "If interest rates are low, then housing starts are up. If housing starts are up, then marriage rates are high. If interest rates are low, then the economy is good. The economy is not good. ...
1
vote
0answers
70 views

Propositional logic question for designing new proof system

Try to solve question from Logic in Computer Science 2nd by Huth & Ryan Natural deduction is not the only possible formal framework for proofs in propositional logic. As an abbreviation, we ...
3
votes
1answer
138 views

Soundness of a rule of a proof system with respect to the truth tables?

I have the following question: "Explain the concept of the soundness of a rule of a proof system with respect to the truth tables" Would it be correct to state the following: "A rule of a proof ...
3
votes
2answers
114 views

is $p \land (p \lor q)$ a tautology?

I would just like to know whether my work is correct before I continue on with the rest of the questions. $$p \land (p \lor q)$$ $$p \land (\lnot p \rightarrow q)$$ $$(p \land \lnot p) \rightarrow ...
1
vote
0answers
32 views

Deriving ¬R from {R↔(R∨(P∧¬P)),R↔¬P,¬P→(P↔(Q→Q)),P→Q} [duplicate]

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
1
vote
2answers
82 views

Deriving $\neg R$ from $\{R↔(R∨(P∧¬P)), R↔¬P, ¬P→(P↔(Q→Q)), P→Q\}$

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
1
vote
0answers
127 views

Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ ...
0
votes
2answers
61 views

Undirected Graph Bipartite

I am unsure how to approach this problem: Prove that an undirected graph is bipartite if and only if there are no edges between nodes at the same level in its BFS tree. (An undirected graph is ...
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 )$$ ...
1
vote
3answers
88 views

Does statement 1 imply statement 2?

1) (For some $t, P(t).) \implies Q$. 2) For all $t, (P(t) \implies Q).$ I think so, and my reasoning is this: for Q to be true, we just need P to be true for some t. Therefore, over the range of ...
1
vote
1answer
215 views

How to prove these using natural deduction

I'd like to prove the following logical equivalence by using natural deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x)) \implies q.$$ As far as I'm concerned to show that two ...
2
votes
3answers
86 views

Is $(m \Leftrightarrow m) \Leftrightarrow (m \Rightarrow m)$ a tautology, contradiction or contingent?

Is this a Tautology, contradiction or contingent? $(m \Leftrightarrow m) \Leftrightarrow (m \Rightarrow m)$ My answer is that It is a tautology. But what is yours? Can someone please explain with ...
2
votes
2answers
1k views

Using DeMorgan's Laws to complement a function

Using DeMorgan's Law, write an expression for the complement of $F$ if: $F(x,y,z) = x(y' + z)$. $F=x'+(y'+x)'$ $F(x,y,z) = xy + x'z + yz'$ $F=(xy)'(x'z)'(yz')'$ $F(w,x,y,z) = xyz' (y'z + x)' + ...
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?
2
votes
2answers
82 views

formula !x using only x and NAND

Hi how would I get formula that is equivalent to NOT X, using only the variable X and the NAND connective? Regards J
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
1answer
56 views

Rooted Trees & Induction

So I am a little stumbled upon this question: A full binary tree is a rooted tree where each leaf is at the same distance from the root and each internal node has exactly two children. Inductively, a ...
1
vote
5answers
93 views

How to solve this class of problems?

I was presented with the following problem: Ricardo, Rogério and Renato are brothers. One of the is a medic, the other one is a teacher and the other one is a musician. It is known that: ...
0
votes
0answers
37 views

why is ¬(P∧Q) equivalence to ¬P∨¬Q and how we prove it? [duplicate]

why is ¬(P∧Q) equivalence to ¬P∨¬Q ( De Morgan's laws) and how we prove it with out Using truth table?
2
votes
3answers
70 views

propositional calculus?

I'm very stuck on this question in my High School class. Atomic Sentances: I – I am hungry M – I will eat pie V - I will become lazy. B - I will be happy. Hypothesis: H1 – $I \implies M \land ...
0
votes
1answer
79 views

Why is $\neg(P\land Q)$ equivalent to $\neg P\lor\neg Q$? [closed]

Why is $\neg(P\land Q)$ equivalent to $\neg P\lor\neg Q$, and how do we prove it? Thanks!
2
votes
2answers
78 views

What suffices for showing $p \Leftrightarrow q \Leftrightarrow r$?

I have to show that $p \Leftrightarrow q \Leftrightarrow r$ where $p,q,r$ are logical sentences. Is it true that it suffices to show only $p \Rightarrow q \Rightarrow r$?
1
vote
2answers
36 views

Propositional logic-Predicates

I have this problem in my Discrete structures course Show why : ∀x P(x) ∨∀x Q(x) is not logically equivalent to ∀x(P(x)∨Q(x)) . Please help solve this
0
votes
1answer
173 views

Source request for Natural Deduction Exercises

What is your source of choice to get exercises on Natural Deduction? I already solved everything in Logic for Artificial Intelligence & Informational Technology and just about everything I could ...
2
votes
1answer
77 views

Explain the Absorption Law

I am currently in a Discrete Math class and reviewing some of my terminology and I don't really understand the Absorption Law. I am not looking for a proof or a truth table but an explanation in ...
1
vote
2answers
78 views

Expressing the negation of $[\neg(p\land\neg q)]\land\neg r$ without $\neg,\land,\lor$

Negate $[\neg(p\land\neg q)]\land\neg r$ and replace the resulting formula by an equivalent which does not involve $\neg, \land$ or $\lor$. Can someone tell me how to get through this question? ...
0
votes
1answer
24 views

Where to start when converting a logical formula to English?

I've got this problem with some atomic sentences, I was just wondering whether when converting it into English I needed to do the brackets first along with precedence or whether I just work my way ...
1
vote
2answers
150 views

Propositional Logic: Models/Counter-Models

I conducted an extensive search on Google, Math.StackE and ProofWiki before posting. Given the following task: (Given a single specification) Use truth tables to check if the specification is ...
4
votes
2answers
177 views

Natural deduction: $(\neg q \to\neg p)\vdash(p\to q)$ without Modus Tollens

Can anyone help me to obtain this result in natural deduction, without using modus tollens: $$(\neg q \to \neg p) \vdash ( p \to q)$$
1
vote
2answers
134 views

Interested in a “more fundamental” proof for basic properties of the logical connectives

Starting with the classical propositional logic, is there a rather canonical way to prove that $$p\wedge q=q\wedge p$$ for the commutativity of the conjunction and analogously for the other properties ...
0
votes
1answer
77 views

Length of a formula in propositional logic

I've seen the following problem on a past exam question: Show that the length of a formula in $\mathscr{L}$ is equal to $4m+n+1$, where $m$ is the number of binary connectives and $n$ is the number ...