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)

0
votes
0answers
18 views

How to recognize if a there is a logical entailment?

I have evaluated each of the formulas in gamma and they are not tautologies. Then, I have no idea... Can someone help?
0
votes
0answers
64 views

Let Γ = {p∧q,(¬p)∨q,p∨r}. Is it true that Γ ⊢ r?

I"m not sure how to solve this type of question. Here is the problem in more detail, and a similar problem: I know that given this set of formulas I'm supposed to show if its possible to deduce r ...
-1
votes
0answers
20 views

Equivalent sentences using logical connectives

Using only logical connectives implication ($\to $) and negation ($\lnot $), write a sentence equivalent to the sentence: $$ (p \land q ) \lor r $$ Using logical connectives disjunction ($\lor$) ...
0
votes
2answers
57 views

Finding a formal deduction from an empty set of premises

I can't seem to make sense of any of this. I'm given a set of axioms schemes, modus ponens as the inference rule and I'm supposed to find a formal deduction. The question (question 1) is here. It ...
-5
votes
1answer
63 views

Which if the following three propositions are logically equivalent? [on hold]

Which if the following three propositions are logically equivalent? $(p \wedge q) \Rightarrow (p \wedge r)$ $p \wedge (q \Rightarrow (p \wedge r)) $ $(\lnot p) \vee (\neg q) \vee (r \wedge p)$ ...
2
votes
4answers
79 views

Question about logical implication $P\to Q$ [duplicate]

Having come across mathematical logic, a question suddenly came into my mind. We commonly know that the truth value of $P\to Q$ given as: $\begin{matrix} P&Q&P \Rightarrow Q \\ ...
0
votes
0answers
29 views

A mathematical statement is logically equivalent to a related statement

I have to finish the statement: A mathematical statement and its ____________ are logically equivalent. My guess is contrapositive but I do not think that's right. Any help will be appreciated. ...
2
votes
3answers
36 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
2
votes
1answer
72 views

Problem with proving formally tautology using given rules

Using the rules below prove that the following assumeptions leads to the following conclusion by tautology. $A\vee B \vee C, A\to C, B\to C \Rightarrow C$ What I did: $A\vee B \vee ...
1
vote
1answer
33 views

Is the True clause considered the proof of resolution refutation

So, basically I have the sentence $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P \Rightarrow R))$$ and it was asked to prove it by resolution refutation. On the ...
0
votes
0answers
21 views

Logic negate and simplify

Negate and Simplify: [(pvq)->~r]v~q Can someone show me step by step how to go about this. I am a little confused about negating over an implication.
1
vote
1answer
31 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
1
vote
1answer
50 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
46 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
24 views

How can I translate it into Logic sentence? [closed]

Let $p$ denote "it is snowing." So how can I translate the following into symbolic logic? "It is not snowing, but snowing." Please help me.
2
votes
1answer
54 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
1
vote
2answers
44 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
2
votes
2answers
56 views

Every element of the empty set has three toes true or false? [duplicate]

This is a bonus question that we have and I cannot figure it out. Any help would be great! Is the proposition Every element of the empty set has three toes true or false? Explain your answer
1
vote
0answers
27 views

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ [duplicate]

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ Or how do one go about showing that the former is not a proposition. I've just started reading Dalen's Logic and ...
1
vote
2answers
39 views

Prove that it is a tautology

Let $P$, $Q_1$, $Q_2$ be some well-formed propositional formulas. Show that if $P\vee Q_1$ and $\neg P\vee Q_2$ are tautologies then $Q1\vee Q2$ is a tautology.
0
votes
3answers
34 views

Question about negating implied propositions

I'm negating this proposition: "If you study you will not fail." I'm using proposition P: "You study" and proposition Q: "You will fail." The original statement can be written as "$P → ¬Q.$" My ...
1
vote
4answers
71 views

Basic logic question: Can $\neg p \implies p$ be true?

Can $\neg p \implies p$ be true? How about $p \implies \neg p$? I was told yes, but it doesn't make sense to me. Any help would be appreciated!
0
votes
1answer
33 views

Given $p \rightarrow q$ and p are true, show $q ∨ r$ is true using rules of inference

I have a question from computing mathematics which I am not really able to prove. Given that $p \rightarrow q$ and $p$ are true, show that $q \lor r$ is true using rules of inference. Any ...
1
vote
2answers
77 views

Proof of a theorem in Hilbert's system

I have been trying to prove that the propositional formula $ \big( \alpha \rightarrow \lnot \beta \big) \rightarrow \big((\alpha \rightarrow \beta) \rightarrow \lnot \alpha \big)$ is a theorem in ...
1
vote
4answers
70 views

Need Hints Prove “$((\neg \alpha \to \alpha) \to \alpha) $” Using Axiom 1,2,3 and MP and deduction theorem

$((\neg \alpha \to \alpha) \to \alpha) $ Hi, I am trying to prove this. Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I ...
1
vote
1answer
18 views

Proposotional logic derivation

Show that (φ ∧ ψ) ↔ ¬(φ → ¬ψ) is derivable. I have derived ¬(φ → ¬ψ) from (φ ∧ ψ) by assuming (φ → ¬ψ) and (φ ∧ ψ) and deducing a contradiction. By cancellation of the hypotheses I can then conclude ...
0
votes
1answer
15 views

Conjuctive normal form of $(p\wedge(q\implies r))\implies s$

I am asked to write this in CNF without using truth tables. This is what I worked out so far: $$(p\wedge(q\implies r))\implies s \\ \neg(p\wedge (q\implies r)) \vee s\\ (\neg p \vee \neg(\neg q \vee ...
1
vote
1answer
39 views

Prove that simple conditional statement is tautology

This should be pretty easy, but I don't know how to turn the conditional statement into a tauntology. The statement is: $$ (p \land q) \to p$$ I am able to turn it into: $$ (\lnot p \lor ...
0
votes
4answers
68 views

Solve this proof using tautologies (no truth tables)

I am having trouble solving this problem using tautologies (no truth tables). Hypotheses: $t \rightarrow s,\;\; d \rightarrow (u \vee t)$ Conclusion: $d \rightarrow ( u \vee s)$
1
vote
1answer
38 views

Show that the function is an isomorphism between two $L$-structure.

The function: $$f: \mathbb{R} \longrightarrow (-1, 1)$$ $$ x \rightarrow \frac{x}{1 + |x|}$$ is an isomorphism between $\langle\mathbb{R}, <, =\rangle $ and $\langle(-1, 1), <, =\rangle$ where ...
0
votes
1answer
44 views

Logical Consequences and Ordered Fields.

How do I show that these two: $1.$ $\forall x(0 < x \rightarrow (-x) < 0)$ $2.$ $\forall x \forall y \forall z((x<y \wedge z<0) \rightarrow (y *z) <(x*z))$ are logical consequences ...
1
vote
1answer
40 views

Conversion from English Language to Logic Symbols

I have a problem in an example of Discrete Mathematics which my teacher worked in his lecture. He gave an argument and proved it that his argument was not valid, but the validity of argument is not ...
1
vote
1answer
99 views

Is infinite boolean algebra atomless?

I got two questions: 1) Does there exist an infinite Boolean algebra which contains an atom? I answered yes. 2) Does there exist an infinite Boolean algebra B such that for every b contained in B ...
1
vote
1answer
27 views

Prove that if $T$ is maximal consistent theory then $T$ is satisfiable

I want to prove that If $T$ be a maximal consistent subset of the set of all formulas then $T$ is satisfiable. By using the following facts I have proved for a maximal consistent $T$; ...
1
vote
1answer
121 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 ...
0
votes
1answer
34 views

Modus ponens proof

I'm trying to prove that $\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, $\bullet \varphi \approx (\varphi \to \varphi)$ Axiomas are the followind: A1) $\neg\neg\bullet\bullet\varphi$ A2) ...
0
votes
1answer
20 views

How to decide if propositional function is complete

I have two 3-ary propositional functions given by the table $$ \begin{array}{|c|c|c|c|c|} v(a) & v(b) & v(c) & v(f(a, b, c)) & v(g(a, b, c)) \\ \hline 0 & 0 & 0 & 1 & ...
-1
votes
1answer
52 views

To prove that an argument is valid with the rules of inference of propositional logic

Use propositional logic to prove that the following argument valid : $$(A→ ¬B) ∧ [D ∨ ¬ (C ∧ ¬B)] ∧ C → (A→D)$$
0
votes
1answer
15 views

Predicate formula to propositional formula

I have: $$\begin{align} \exists x \forall y P(x,y) \\ \end{align}$$ where $$\begin{align} M=\{a,b\} \\ \end{align}$$ I need to convert this formula to propositional logic. I know that if ...
0
votes
1answer
59 views

proof that p implies q entails not p or q [duplicate]

I could easily prove $\neg P \lor Q$ entails $P \rightarrow Q$. It is well known that $P \rightarrow Q$ entails $\neg P \lor Q$ but I couldn't find a way to prove it. Although there is the ...
0
votes
1answer
47 views

Modus ponens proof in system L(¬,→,∙)

I'm trying to prove $\neg\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, where $\bullet$ is constant truth, i.e. $\bullet \varphi \approx (\varphi \to \varphi)$ Using modus ponens with ...
2
votes
1answer
20 views

Three atomic forms expression both in disjunctive and in conjunctive form?

we know that A v B is in both conjunctive and in disjunctive normal form. we also know that A ^ B is in both conjunctive and in disjunctive normal form. Does it follow from this, that A v B v C is ...
1
vote
1answer
41 views

Don't really understand the absorption law

I don't really get the absorption law, specifically in this case: $$ (\lnot p \lor q) \land (\lnot r \lor q) \equiv (\lnot p \land \lnot r) \lor (\lnot p \land q) \lor (q\land \lnot r) \lor (q \land ...
0
votes
3answers
33 views

Logical Expression : Is it same or not?

I have $p\rightarrow \left ( q\wedge r \right )$, If i negate it: It will become like below: $\lnot \left ( p\rightarrow \left ( q\wedge r \right ) \right )$ $\lnot \left ( \lnot p\vee \left ( ...
1
vote
1answer
29 views

What is the conjunctive normal form of the boolean constant TRUE?

I have the following problem: Is TRUE (or 1) a logically equivalent formel in conjuctive normal form to a tautology? How can I build the conjunctive normal form ...
1
vote
1answer
29 views

using the elimination rule in natural deduction

Prove that $$(A ∧ B) \to C ⊢ A \to (B \to C)$$ Am I using the conjuction elimination rule correctly? Or am I assuming too much? $(A ∧ B) \to C$ (Given) $A \to C , B -> C$ (∧E 1) $A ...
2
votes
4answers
59 views

Prove $Q \rightarrow \neg(Q \rightarrow \neg P)$

I have an exercise about proving statements: Suppose that P is true. Prove that Q → ¬(Q → ¬P ) is true Givens: $P$ $Q \rightarrow \neg P$ Goal: $\neg Q$ which I simply prove ...
3
votes
1answer
25 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
2
votes
3answers
69 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
4
votes
4answers
65 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...