2

誰かが次の質問で私を助けてくれることを望んでいました.答えが最善ですが、正しい方向に私を向けることができれば. 私は大学の最終学年の学生で、これらの質問は形式的方法に関する以前の試験からのものであり、今年の論文の準備ができている答えを知っていればできます。私たちの講師は最高ではないようで、これについて多くをカバーしていないため、正確な答えを見つけることは不可能であることが証明されています. グーグルはあまり役に立ちませんでしたし、推奨された本もありませんでした.

1 - ∃x • P (x) が ¬∀x • ¬P (x) と論理的に等価であり、∀x ∈ S • P (x) が ∀x • x ∈ S ⇒ P (x) を意味すると仮定すると、 ∃x ∈ S • P (x) は、∃x • x ∈ S ∧ P (x) を意味します。

2 - 定義を示すために証明する必要がある 2 つのステートメントを説明してください。

max(i, j)
if i>j
then i
else j

仕様の正しい実装です:

max(i : Z, j : Z)r : Z
pre true
post (r = i ∨ r = j) ∧ i ≤ r ∧ j ≤ r
4

2 に答える 2

2

1つ目は、実際には、指定された論理的等価物と他の2つのよく知られた論理的等価物を使用したシンボルの操作です。

(1) ∃x • P(x) is logically equivalent to ¬∀x • ¬P(x)
(2) ∀x∈S • P(x) means ∀x • x∈S ⇒ P(x)

∃x∈S • P(x)
== ¬∀x∈S • ¬P(x) (from (1))
== ¬∀x • x∈S ⇒ ¬P(x) (from (2))
== ¬∀x • ¬x∈S v ¬P(x) (from def. of ⇒)
== ¬∀x • ¬(x∈S ∧ P(x)) (from ¬A v ¬B == ¬(A ∧ B))
== ∃x • x∈S ∧ P(x) (from (1) -- the other way around)

max(i, j)2つ目は、の結果が2つのパスのいずれかに沿って計算されることを認識する必要があります。1つはwhen i<j、もう1つはwhen i>=j（の論理否定i<j）です。

だからあなたはそれを示す必要があります

  1. if true ∧ i<j（precondition）、then (r=i ∨ r=j) ∧ i≤r ∧ j≤r（post condition）、および
  2. if true ∧ i>=j（precond。）then (r=i ∨ r=j) ∧ i≤r ∧ j≤r（post cond。）、

rの結果はどこですかmax(i, j)

于 2012-05-23T12:40:55.743 に答える