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
0answers
61 views

how to prove the following formula via natural deductions $a ∧ ¬a \vdash b ∧ ¬b$

Hi I am trying to prove the following formula via natural deduction and this is what I have so far. I am not sure however if this is entirely correct. If I could get some verification and be pointed ...
-1
votes
1answer
37 views

Tautology example [closed]

How to verify if this logical statement is a tautology? AB+BCD+AC=NOT(AB+AC) I have seen all the posibilities but I am not sure that is tautology. And I have to solve it and to do all the ...
1
vote
0answers
48 views

Generating all logic propositions

I'm looking for a way of generating all logic propositions (propositional calculus) in an "algorithmic" way. The equivalence is symbolic, so $\neg\neg a \neq a$ and $\neg a \lor b \neq a \implies b$, ...
0
votes
1answer
30 views

Prove Tautology

Can you please prove the equation (~pVr)^(pVq)->(qVr) without using truth table. I have tried and ended up half way ~[(~pVr)^(pVq)]V(qVr) ~(~pVr)V~(pVq)V(qVr) (p^~r)V(~p^~q)VqVr (p^~r)VrV(~p^~q)Vq
0
votes
1answer
24 views

How to specify the corresponding line of a truth table in a formula?

How to specify the corresponding line of a truth table in a formula: $$p \to (\neg q \lor (q \to p))$$ $p$ evaluates to $F$ and $q$ evaluates to $T$. I want to know the method followed to find this....
2
votes
1answer
30 views

How to handle degrees (numerical attributes) in logic? How to model “quantitative changes lead to qualitative changes”?

I am using logics (propositional, predicate, modal) to model one domain, but there are variables that have non-boolean domains, these variables are degrees (it is sufficient that they are degrees, ...
1
vote
2answers
70 views

What will the declarative sentence No shoes, no shirt, no service be in propositional logic?

I need to write the following declarative sentence in propositional logic. No shoes, no shirt, no service. My solution is: ~p,~q, ~r , is it correct or do i need to use implication -> instead
2
votes
1answer
56 views

All hill-stations have a lake. Ooty has two lakes?

All hill-stations have a lake. Ooty has two lakes. Which of the statement(s) below is/are logically valid and can be inferred from the above sentences? $(i)$ Ooty is not a hill-station. $(ii)$ No ...
0
votes
1answer
46 views

Propositional Resolution - How to prove?

I was given the following argument which is valid. I must prove it using propositional resolution. ((A $\rightarrow$ B) $\rightarrow$ C) (C $\rightarrow$ (D · E)) $∴ $ (B $\rightarrow$ D). So ...
0
votes
2answers
40 views

Solving rules of inference questions from Discrete Maths Rosen and I am confused on a step

So the question is, Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then ...
0
votes
0answers
28 views

Consistency of a Knowledge base (resolution)

To prove Q is a logical consequence of a knowledge base KB, it is possible to add not(Q) to KB and perform resolution, and reach an empty clause. But how is it possible to show Q is not a consequence ...
0
votes
1answer
112 views

Logical Equivalence as an equivalence relation

I've been given the following problem for homework and I'm struggling with where to begin "Suppose we have a set of 5 propositional variables, denoted L. By considering logical equivalence, what is ...
0
votes
3answers
36 views

Show that a set of logical connectives is expresively complete

I've been trying to figure this out for hours now, there doesn't seem to be ample resources online for my skill level to solve such a question: Show that a set of connectives {∧,¬} is expressively ...
1
vote
2answers
20 views

substitutional interpretation of quantifiers: examples?

About the differences between propositional logic and (first order) predicate logic, given that if my basis is propositional logic I have to substitute the universal and existential quantifiers with ...
0
votes
2answers
51 views

Propositional logic vs predicate logic: examples?

About the difference between the propositional logic and the (first order) predicate logic-> can you give me one or more remarkable examples which underly the differences and the similarities ...
1
vote
2answers
47 views

If $P \iff Q$ is true and $P \land Q$ is false, do we arrive at a contradiction?

If $P \iff Q$ is true and $P \land Q$ is false, do we arrive at a contradiction? So I know that $P$ is false and $Q$ is false. And I also know that the biconditional $P \iff Q$ is equivalent to $$\...
0
votes
0answers
37 views

Proof of Replaceability of Equivalent Formulas by Structural Induction

My class discussed the following theorem for which I wasn't able to make it to class. Its proof is supposed to involve structural induction but I am stuck in the inductive step... Let B |=| C. If A' ...
2
votes
1answer
42 views

Prove the following formula is a contradiction: (~(A --> B)) ^ (B V ~ A)

I have worked with this truth table now - is everything correct or, do I miss something?
2
votes
1answer
36 views

Disjunctive Normal Form for Fuzzy Logic

I'm asked to prove that every propositional assertion in Fuzzy Logic, expressed using the standard propositional connectives $\{\land, \lor,\lnot, \rightarrow, \leftrightarrow\} $ can be expressed in ...
1
vote
3answers
65 views

A riddle in logic and propositional logic

The professor gave the class a riddle Suppose the following two statements are true: I love A or I love B If I love A, then I love B Does it necessarily follow that I love A? Does it necessarily ...
0
votes
1answer
47 views

Knights and Knaves. Translating an “Either or” statement into propositional logic

I'm studying for a midterm for my logic course. I was going through the lecture slides and came across this problem. You are on an island of kights and knaves. Knights always tell the truth and knaves ...
-1
votes
1answer
35 views

Propositional Logic conversion (English to Language of Logic)

I have a confusion about the below proposition logic: Let p and q be the propositions p :It is below freezing. q :It is snowing. Write these propositions using p and q and logical connectives (...
1
vote
1answer
31 views

Conditional Proof and lemmas

I'm trying to solve a problem of propositional logic. The problem is this: $(H\vee P \vee L) \wedge (¬H \Rightarrow ¬P \vee ¬L ) \wedge (¬L\Rightarrow ¬P ) \wedge ¬H \Rightarrow L$ So I'm solving ...
1
vote
1answer
31 views

If the TV is not on sale, I will not buy it?

If the TV is on sale, I will buy the TV. The TV is not on sale. $\therefore$ I will not buy the TV. $p$: The TV is on sale. $q$: I will buy the TV. First statement above: $p\implies q$ Second ...
0
votes
1answer
49 views

Formally prove the following equations using propositional logic

p ∧ ¬p $\vdash$ q ∧ ¬q p ∧ r ⇒ q ∧ r , p ∨ r ⇒ q ∨ r $\vdash$ p ⇒ q I have literally been trying to figure these out all morning and I'm desperately stuck now. We have to prove them using ...
-1
votes
1answer
74 views

What type of proof is $P\Rightarrow P$?

I have this problem statement: Let $P$ a proposition, now if we suppose $P$ is $\texttt{true}$, and the proof gives $P$. What demonstrates this? Solution: $\ \ P\Rightarrow P$ $\equiv \langle \...
0
votes
0answers
36 views

Show that the following argument is valid by Chain of Reasoning

I just recently started proving in propositional logic and everything is going well until I came across this problem. I tried to use different methods and it is going me out of nowhere. I read ...
0
votes
1answer
47 views

Negation of a Logical Statement; Proper English Translation

Consider the following two propositions: $p$: We can go to Cancun. $q$: We can go to Iceland. Using symbolic notation, a) Form the conjunction ($\land$). $p \land q$: We can ...
1
vote
1answer
34 views

Propositional calculus resolution on pigeonhole principal

Here are my premises: A v B, C v D, E v F, ~A v ~C, ~B v ~D, ~A v ~E, ~B v ~F, ~C v ~E, ~D v ~F Is this even possible? I can't get it down to a unit clause because a new clause is added back in ...
1
vote
0answers
31 views

Defining the differentiability of a multivariable function (if/then)

I'm trying to understand differentiability for multivariable functions and am thoroughly confused by the introduction (and the direction of implications in a certain definition) I'm given the ...
0
votes
1answer
50 views

proof verification for converting sentence into propositional logic

Hi I wanted to know if I have translated this sentence correctly, The sentence is; ...
0
votes
1answer
35 views

Logically inferred from the given statements?

Consider the following statements relating to the level of poker play of four players $P, Q, R$ and $S$. $I. P$ always beats $Q$ $II. R$ always beats $S$ $III$. $S$ loses to $P$ only sometimes $IV....
0
votes
2answers
59 views

Prove each equivalence by using the rules for semantic equivalence

Having some issue with some logic - the examples I've been provided with arn't very helpful so I can have no idea where to start. The question is to prove; ...
0
votes
3answers
59 views

How to show that $\lnot p \to (p \to q)$ [closed]

How can I show using formal logic that $\lnot p \to (p \to q)$? I'm looking for hints towards a propositional calculus proof, and would not accept an answer consisting solely of truth tables.
0
votes
2answers
35 views

Is ( ¬p AND (p OR q) ) AND ¬q a contradiction?

As We Know That p AND (q OR r) = (p AND q)OR(p AND r) we have ...
2
votes
2answers
72 views

how to prove the following propositional formula using semantic equivalence

Hi Guys I am trying to prove the following formula using the rule below ...
0
votes
2answers
31 views

Is the following statement equivalent?

Is the following statement equivalent: $((A \vee \neg C) \wedge ((\neg B) \leftarrow C)) \vee \neg (A \wedge B) \equiv (\neg A \vee \neg B \vee \neg C) $ Our prof gave us an exercise with this ...
0
votes
1answer
39 views

Trouble with step 2 resolution calculus

I need to prove T ⊨ A v B with the resolution calculus from a set T. Step 1 Transform T into a set of clauses (CNF). Clause 1 = A v ¬C Clause 2 = C v A v B Step 2 Try to find a resolution ...
1
vote
2answers
55 views

How to demonstrate this tautology using equivalences?

I have this tautology $(P \wedge (P \rightarrow Q) \wedge (Q \rightarrow R)) \rightarrow R$ I couldnt prove it by using equivalences. Using Definition of implication and then using negative ...
0
votes
2answers
99 views

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use ...
0
votes
1answer
20 views

Propositional variables in semantic equivalence

I'm learning the semantic equivalence rules/laws in propositional logic, but I'm confused by what the propositional variables in the rules are supposed to represent. For example, the associative ...
0
votes
1answer
43 views

Resolution calculus converting into set of clauses

Here is $T$: $a \lor \neg b$ $\neg a \lor (c \land d)$ $b$ I am suppose to use resolution calculus to prove that $T \models d \land b$ holds. As in the first step, we translate $T$ ...
0
votes
0answers
35 views

Is (A v C) v B in conjunctive normal form?

I need T to be a set of clauses in conjunctive normal form. T = { (¬A ^ ¬C) → B } T = { ¬(¬A ^ ¬C) v B } T = { (A v C) v B } I 'simplified' it to T = { (A v C) v B }, is it in CNF? ...
2
votes
3answers
110 views

$a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent.

Suppose a,b,c and d are statements such that $a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent. Hey, Im ...
1
vote
1answer
43 views

Lambda Calculus Proof: or false (not true) Evaluates to False, using lazy evaluation, Help!

I am trying to learn lambda calculus, and I am currently tackling a few boolean logic questions. I have gotten to one that I am stuck on, and I am looking for a little help proceding. I need to ...
0
votes
1answer
40 views

On the functional-completeness of the sheffer stroke

I have seen functional-completeness (in regards to boolean functions) defined as: A set X of truth-functions (of 2-valued logic) is functionally complete if and only if for each of the five ...
-3
votes
1answer
50 views

Propositional-Calculus/ Set Theory Proof using Identities [closed]

$$(\sim P\,\lor \sim Q)\equiv (Q\to (\sim P\,\lor\sim Q))\land ((\sim P\,\lor \sim Q)\to Q) $$ Can someone demonstrate the identity proof here? I've been trying to figure this out, but with no avail....
1
vote
1answer
45 views

Why is this predicate false?

I am stumped at my professor's answer to this predicate logic. all x and y are natural numbers. ∃y∃x(x >= y) I think it is true, since there is a pair $(...
-1
votes
1answer
55 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
-1
votes
1answer
72 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) \...