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)

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
194 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
135 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
96 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
125 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
113 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
214 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
171 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
76 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
147 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
175 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
132 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
75 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 ...
0
votes
0answers
14 views

predicate calculus and using the Euclidean algorithm [duplicate]

So I have this problem which I can't seem to prove. Define the predicate RP(a,b) for positive naturals a and b as follows. RP(a,b) is defined to be true if and only if one of the following is true: ...
0
votes
2answers
183 views

$(p\lor \lnot q) \land (q \lor ¬r) \land (r \lor ¬p)$ is true $\iff$ $(p, q, r$ all have the same truth-values$)$

Explain why $(p\lor \lnot q) \land (q \lor ¬r) \land (r \lor ¬p)$ is True when p,q,and r have the same truth value and it is false otherwise. (Without using a truth table ) Please help me solve this ...
1
vote
2answers
179 views

Proving ${\sim}(p \mathbin\& q)$ implies ${\sim p}\mid{\sim q}$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~(p & q), that ~p | ~q . Any ideas on how I should proceed; I have no idea...?
1
vote
3answers
72 views
1
vote
2answers
329 views

Proving ${\sim p}\mid{\sim q}$ implies ${\sim}(p \mathbin\& q)$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~p | ~q , that ~(p & q). Any ideas on how I should proceed?
1
vote
3answers
359 views

I need to show the validity of the below arguments by using a truth table

I need to show the validity of $P \rightarrow Q$ $P \rightarrow R$ $\therefore P \rightarrow (R \wedge Q)$ Can i just show the truth table for $P \rightarrow Q$ and the truth table for ...
1
vote
2answers
123 views

Solving logic word problems

So I have a number of statements of this "murder" word problem that I must solve. I will try and simplify them as much as possible. So I have these 4 different facts: If Sarah was drunk then either ...
1
vote
1answer
95 views

Discrete math proof issue

This is a question from my discrete math quiz. I was asked to prove there exists a Q(x). I used Disjunctive Syllogism to prove it. I was marked incorrectly because I used two different variables in ...
0
votes
1answer
67 views

Proof methods Discrete Math

Claim: for any integers m and n, if $7m + 5n = 147,\,$ then $m$ is odd or $n$ is odd a) state the converse of the claim b) state the contrapositive of the claim. c) use proof by contrapositive to ...
0
votes
2answers
134 views

Propositional logic: Proving equivalence

Given two logical forms: $(p \implies q) \lor (q \implies r)$ and $p \implies r$, are they logically equivalent? Explain your answer. Thanks! My answer is no and I used coversion theorem to show ...
0
votes
1answer
57 views

Making first order logic statements

I'm working on an assignment that deals with predicate calculus, and I'm trying to put sentences into first order logic statements. I've got the hang of most of them, but I'm not quite sure how to do ...
0
votes
2answers
109 views

Natural Deduction: $(p \lor q)\to r\vdash p \to r$ and $p\to\neg q\leftrightarrow(r\lor s),\neg s\vdash (p\land \neg q)\to r$

I am having trouble applying Natural Deduction rule and solving these two questions. How do I start this. \begin{align} \{(p\lor q)\to r\}&\vdash_{\sf ND} p\to r\\ \{p\to\neg ...