Tagged Questions

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
1answer
20 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
25 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
56 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
22 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
60 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
59 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 ? ...
2
votes
2answers
23 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
-3
votes
0answers
25 views

Writing Expressions [on hold]

a “The program is faulty”, s “I will lose my data” d “The disc is full”. Write an expression in terms of a, s and d that exactly represents the proposition “In the case of a faulty program, I will ...
0
votes
1answer
26 views

natural deduction on proving a claim

I am working on this proof and wanted to know if I am using the ID natural deduction rule correctly. Can I just assume B and A based on that rule? ...
3
votes
0answers
96 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
1
vote
1answer
33 views

Translate the following argument into propositional logic, and then assess it for validity.

This is question 9 from exercise 6.5.1 in Smith and Cusbert's Logic: The Drill. It wants a translation and test of validity for the following: Catch Billy a fish, and you will feed him for a ...
0
votes
0answers
35 views

Prove that the truth value of $x_1 \lor x_2 \lor \ldots \lor x_n$ does not depend on how the formula is parenthesized

So the question is: Generalized Associativity of $\lor$. Prove that, for all positive integers $n$, all ways of parenthesizing the following logical statement have the same truth value: $$x_1 \lor ...
2
votes
2answers
50 views

Prove $\lnot \lnot B$

Prove: $\lnot \lnot B$ from $\lnot \lnot A \implies \lnot \lnot B, \lnot(A \implies B) $ I cant use excluded middle: $B \lor \lnot B$ So I choose $\lnot B$ as hypothesis and will try to get $B$ ...
3
votes
1answer
52 views

Why is a not-not-p invalid in a logical clause?

I have an assignment and it states that while $(p \vee q) \vee \lnot r$ is valid, $(p \vee q) \vee \lnot(\lnot r)$ is invalid in a logical clause, but I don't see why. A clause is described as being ...
0
votes
2answers
36 views

For any set of formulas in propositional logic, there is an equivalent and independent set

A set of formulas is independent if no proper subset is logically equivalent to it. Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.
1
vote
1answer
22 views

Distribute ANDs over ORs in this sentence

Can someone explain how we turn the sentence $$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because ...
1
vote
3answers
45 views

Reverse of Deduction Theorem

Why is it "easy to see" that if $S \vdash (A\to B)$ then $S \cup\{A\} \vdash B$?
0
votes
1answer
36 views

Justify each step in the following proof of Proposition 3.9 (a). I like to know if I'm in the right track and I'm also missing a few of them

Proposition 3.9(a): If a ray r emanating from an exterior point of triangle ABC intersects side AB at a point between A and B, then r also intersects side AC or side BC. proof. (a) Let r= array XD ...
5
votes
1answer
42 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
1
vote
1answer
23 views

propositional-calculus/logic riddle

Two physicists, A and B, and a logician C, are wearing hats, which they know are either black or white but not all white. A can see the hats of B and C; B can see the hats of A and C; C is blind. Each ...
1
vote
1answer
36 views

Proof of Soundness Lemma

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$ We are given the hint to ...
1
vote
1answer
18 views

Inference Lemma Proof?

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$. Proof: Let $\langle ...
0
votes
1answer
29 views

Properties that can be proven with induction on wff's?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\to\}$ and $\textit{propositional symbols}=\{A_n\mid n\in\mathbb{N}\}$ for $n \in ...
1
vote
1answer
41 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
55 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...
1
vote
2answers
27 views

What operation is done first in the following exercise…

Here I have such an exercise: I have to simplify the form of the following expression:$$(p\lor \lnot q)\land(\lnot p \lor q )\lor (p \lor \lnot r)\lor \lnot q$$. I know how to simplify it, but what ...
0
votes
1answer
50 views

Why do you only need to show validity in one world when using trees in institutionist/constructivist logic?

Depicted below, my prof used a tree to prove that an argument is valid according to intuitionist logic. However, I can't find a contradiction in world 0. Why is invalidity ascertained when all ...
4
votes
2answers
207 views

Proof that expression is a tautology

I'm studying to my exam and I have some doubts. The expression: $$¬(P \Leftrightarrow Q) \Leftrightarrow P \oplus Q$$ The objective is to know if it is a tautology. I don't know the result. I made ...
0
votes
1answer
25 views

Propositional Logic meta-variable notation abuse

When defining Formation Sequence, van Dalen (4th edition page 9) says: A sequence $(\varphi_0,\varphi_1,...,\varphi_n)$ is called a formation sequence of $\varphi$ if $\varphi_n=\varphi$ and: ...
0
votes
2answers
32 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: ¬(P ∨ Q) ∨ (¬P ∨ Q) The result: ¬P ∨ Q The objective is to simplify. I'm stuck at (¬P ∧ ¬Q) ∨ ¬P ∨ Q I could make the distributive, ...
0
votes
1answer
25 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: $$ \lnot \lnot P \land \lnot(\lnot\lnot Q \lor\lnot P) $$ The result: $$ P \land \lnot Q $$ The objective is to ...
1
vote
2answers
46 views

prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table

I need to prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table. Please help me to solve it.
0
votes
1answer
36 views

show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent [duplicate]

without using the truth table: Show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent.
1
vote
2answers
60 views

Prove $\;\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor q \lor r$ without use of a truth table.

Without using the truth table, I need to prove: $$\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor r \lor q$$ Up until now, we've been using truth-tables to ...
1
vote
2answers
36 views

Building logical connectives only with $\neg$ and $\to$

We want to show that the only connectives that are absolutely necessary are $\neg$ and $\to$. Meaning we can construct all the others with them. Given $A_1, A_2 \in \mathcal{L_0}$, the set of ...
0
votes
2answers
35 views

Characterizing the collection of automorphisms on $\mathbb{Z}$ with a binary relation.

How can one characterize the collection of automorphisms of integers $\mathbb{Z}$ with the binary relation "$<$"? Or "$>$"? "$=$"? How can we acquire the collection of automorphisms?
0
votes
3answers
68 views
2
votes
2answers
56 views

Proving tautology

Trying to prove if this statement is a tautology: $\neg (p\to q) \to p$ I can simplify the left hand side $\neg (p\to q)$ to $p\land \neg q$, but once I get there I'm stuck.
0
votes
0answers
23 views

How Do I Show that Condensed Derivable Rules of Inference Yield the Same Formula as Using Condendensed Detachment Multiple Times?

If we look at condensed detachment of two formulas $\alpha$ and $\beta$, we can see that D$\alpha$.$\beta$, where $\alpha$ has form C$\alpha$$_a$$\alpha$$_b$ is equivalent to using the rule ...
3
votes
0answers
28 views

Let $\Gamma$ be a set of formulas and $\phi$. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$

This seemed pretty obvious but I wanted to see if my proof made sense: Proof: $(\Rightarrow)$ To derive for a contradiction, suppose that: $\Gamma \models \phi$. That means for all truth assignments ...
1
vote
1answer
86 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
0
votes
1answer
46 views

Propositional formulas, truth assignments proof

Exhibit a propositional formula $\phi$ using only the logical connectives $\neg$ and $\to$ and using all three propositional symbols $A_1,A_2,A_3$ such that for any $\nu$, $\bar{\nu}(\phi)= T \iff \nu ...
2
votes
1answer
33 views

Using semantic tableaux to prove a situation can occur

I am having a wedding and want to prevent fights at the wedding. suppose the following: John will attend if mark or Aston attends. Aston attends if Mark does not Attend If Aston attends, john will ...
2
votes
1answer
68 views

Propositional Calculus: Stating and proving the unique readability theorem in Polish notation

The Language $\mathcal{L_0}$: Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional ...
1
vote
2answers
46 views

Propositional Calculus: Stating and verifying readability and unique readability of a given language $\mathcal{L^*}$

Problem: Consider the set of symbols * and #. Let $\mathcal{L^*}$ be the smallest set $L$ of sequences of these symbols with the following properties: a) The length one sequences ...
1
vote
1answer
32 views

Is $A \vee B$ in its Conjunctive Normal Form?

Since a conjunctive normal form consists of a conjuction of disjunctions, why is, say, $A \vee B$ in the conjunctive normal form?
1
vote
4answers
57 views

Basic question on logic

I have a slight problem in solving the following question. Let $P$ and $Q$ be statements. Which of the following strategies is "NOT" a valid way to show that "$P$ implies $Q$"? Assume that $P$ is ...
2
votes
1answer
52 views

Propositional Calculus: An algorithm to determine whether a finite sequence belongs to $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
1
vote
1answer
25 views

Representing sentences as propositional logic statements

I'm currently studying logical propositions through distance education for a college course and I'd like some assistance and critique on translating simple sentences into propositional logic ...
0
votes
1answer
28 views

Finding proportions…

kindly accept my apology in advance as i am not good in mathematics and this post might be trivial for some of the forum members. Consider I have $100 and I want to distribute among three poor people ...